将二进制左移推广为八进制表示，无需转换

Question

目前我有几行代码用于处理十进制表示形式的二进制字符串，即我有将二进制字符串向左旋转、翻转特定位、翻转所有位以及反转二进制字符串顺序的函数十进制表示法。它们的定义如下：

inline u64 rotate_left(u64 n, u64 maxPower) {
    return (n >= maxPower) ? (((int64_t)n - (int64_t)maxPower) * 2 + 1) : n * 2;
}

inline bool checkBit(u64 n, int k) {
    return n & (1ULL << k);
}

inline u64 flip(u64 n, u64 maxBinaryNum) {
    return maxBinaryNum - n - 1;
}

inline u64 flip(u64 n, u64 kthPower, int k) {
    return checkBit(n, k) ? (int64_t(n) - (int64_t)kthPower) : (n + kthPower);
}

inline u64 reverseBits(u64 n, int L) {
    u64 rev = (lookup[n & 0xffULL] << 56) |                 // consider the first 8 bits
        (lookup[(n >> 8) & 0xffULL] << 48) |                // consider the next 8 bits
        (lookup[(n >> 16) & 0xffULL] << 40) |               // consider the next 8 bits
        (lookup[(n >> 24) & 0xffULL] << 32) |               // consider the next 8 bits
        (lookup[(n >> 32) & 0xffULL] << 24) |               // consider the next 8 bits
        (lookup[(n >> 40) & 0xffULL] << 16) |               // consider the next 8 bits
        (lookup[(n >> 48) & 0xffULL] << 8) |                // consider the next 8 bits
        (lookup[(n >> 54) & 0xffULL]);                      // consider last 8 bits
    return (rev >> (64 - L));                               // get back to the original maximal number
}

查找[]列表定义为：

#define R2(n) n, n + 2*64, n + 1*64, n + 3*64
#define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
#define REVERSE_BITS R6(0), R6(2), R6(1), R6(3)

const u64 lookup[256] = { REVERSE_BITS };

除了最后一个之外，所有这些都很容易实现。

我的问题是，您是否知道上述函数对于数字的八进制字符串的任何概括，而仅处理上述十进制表示形式？显然没有进行转换并存储八进制字符串本身（主要是由于性能提升） 对于八进制代码中的 Flip()，a 需要返回字符串中指定位置处带有 8-x 的数字（例如：flip(2576, 2nd power, 2ndposition) = 2376，即 3 = 8-5）。

我确实明白，在八进制表示中，任何与rotate_left或flip类似的公式都是不可能的（也许？），这就是我寻找替代实现的原因。 一种可能性是用二进制字符串表示八进制字符串中的每个数字，换句话说，写为： 29 --octal-> 35 --bin-> (011)(101) 因此处理二进制数集。这是个好主意吗？

如果您对上面的二进制表示代码有任何建议，我欢迎任何建议。

提前致谢，对于这么长的帖子表示歉意！

Answer 1

我对rotate_left的理解，不知道我对问题的理解是否正确，希望这对你有帮助。

// maxPower: 8
// n < maxPower:
// 0001 -> 0010
//
// n >= maxPower
// n:                      1011
// n - maxPower:           0011
// (n - maxPower) * 2:     0110
// (n - maxPower) * 2 + 1: 0111
inline u64 rotate_left(u64 n, u64 maxPower) {
  return (n >= maxPower) ? (((int64_t)n - (int64_t)maxPower) * 2 + 1) : n * 2;
}

// so rotate_left for octadecimal, example: 3 digit octadecimal rotate left.
//   0   1   1 ->   1   1   0
// 000 001 001 -> 001 001 000
//   4   4   0 ->   4   0   4
// 100 100 000 -> 100 000 100
// so, keep:
// first digit of octadecimal number is:
//   fisrt_digit = n & (7 << ((digit-1) * 3))
// other digit of octadecimal number is:
//   other_digit = n - first_digit
// example for 100 100 000:
//   first_digit is 100 000 000
//   other_digit is 000 100 000
// so rotate left result is:
//   (other_digit << 3) | (first_digit >> ((digit-1) * 3))
//
inline u64 rotate_left_oct(u64 n, u64 digit) {
  u64 rotate = 3 * (digit - 1);
  u64 first_digit = n & (7 << rotate);
  u64 other_digit = n - first_digit;
  return (other_digit << 3) | (first_digit >> rotate);
}

翻转，对于基数 8，翻转应该是 7-x 而不是 8-x：

// oct flip same with binary flip:
//   (111)8  -> (001 001 001)2
// flip,
//   (666)8  -> (110 110 110)2
// this should be 7 - 1, not 8 - 1, indead.
//
inline u64 flip_oct(u64 n, u64 digit) {
  u64 maxNumber = (1 << (3 * digit)) - 1;
  assert(n <= maxNumber);
  return maxNumber - n;
}

// otc flip one digit
//   (111)8  -> (001 001 001)2
// flip 2nd number of it
//   (161)8  -> (001 110 001)2
// just need do xor of nth number of octadecimal number.
//
inline u64 flip_oct(u64 n, u64 nth, u64 digit) {
  return (7 << (3 * (nth - 1))) ^ n;
}

简单的反转。

inline u64 reverse_oct(u64 n, u64 digit) {
  u64 m = 0;
  while (digit > 0) {
    m = (m << 3) | (n & 7);
    n = n >> 3;
    --digit;
  }
  return m;
}

Answer 2

@Qant123：

关于八进制反转的惰性方法的快速说明：

   000001 010011 100101 110111
    0  1   2  3   4  5   6  7

1. 000001 010011 100101 110111 - sequential bit-string 000-111
2. 111110 101100 011010 001000 - bit-invert them
3. 000100 010110 001101 011111 - reverse the entire string all at once

   000100 010110 001101 011111
   [0][4] [2][6] [1][5] [3][7]

瞧，现在你有了按排序顺序的位反射位串。

同样的方法也适用于十六进制：

00000001001000110100010101100111 10001001101010111100110111101111
11111110110111001011101010011000 01110110010101000011001000010000
00001000010011000010101001101110 00011001010111010011101101111111

=>     [0] 8 [4] C [2] A [6] E ...
   ... [1] 9 [5] D [3] B [7] F

       [0]    8    [4]    C 
          [2]    A    [6]    E
       [1]    9    [5]    D 
          [3]    B    [7]    F

事实上，通过一点点正则表达式，您可以使用不到 5 个循环的简单 for 循环来大量生成这些位反射的位字符串。

由于八进制基数的位数为奇数，任何带有回文位串的数字

(mod 8)

根本不需要改变任何东西。

幸运的是，对于八进制，一半的值是回文 -

   000 010 101 111
    0   2   5   7

因此，人们可以考虑将其作为一种优化捷径 - 例如每当第 1 位和第 3 位匹配（第 1 位 XNOR 第 3 位）时，只需复制它，而不必反映它。