将二进制左移推广为八进制表示而不进行转换

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 需要 return 字符串中指定位置带有 8-x 的数字（例如：flip(2576, 2nd power, 2nd position) = 2376，即 3 = 8 -5).

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

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

提前致谢，抱歉拖了这么久post！

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;
}

将二进制左移推广为八进制表示而不进行转换

Generalizing binary left shift for octal representation without conversion

c++

binary

bit-manipulation

octal