目前，我有幾行代碼可以處理十進制表示中的二進制字串，即我有將二進制字串向左旋轉、翻轉特定位、翻轉所有位和二進制字串的反向順序的函式，所有這些都適用于十進制表示。它們的定義如下：
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() 需要在字串中的指定位置回傳帶有 8-x 的數字（例如：flip(2576) , 2 次方, 2 位) = 2376, 即 3 = 8-5)。
我確實理解在八進制表示中，任何與 rotate_left 或 flip 類似的公式都是不可能的（也許？），這就是我尋找替代實作的原因。一種可能性是用二進制字串表示八進制字串中的每個數字，換句話說，寫： 29 --octal-> 35 --bin-> (011)(101) 因此處理二進制數集。這是個好主意嗎？
如果您對上述二進制表示的代碼有任何建議，我歡迎任何建議。
在此先感謝并為長篇文章感到抱歉！
uj5u.com熱心網友回復：
我對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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/331758.html
上一篇：通過增加頻率對陣列進行排序