Currently I have a few lines of code for working with binary strings in their decimal representation, namely I have functions to rotate the binary string to the left, flip a specific bit, flip all bits and reverse order of the binary string all working on the decimal representation. They are defined as follows:
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
}
WIth the lookup[] list defined as:
#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 };
All but the last one are easy to implement.
My question is whether you know any generalization of the above functions for the octal string of a number, while working only on the decimal representation as above? Obviously without doing a conversion and storing the octal string itself (mainly due to performance boost) With flip() in octal code a would need to return the number with 8-x at the specified place in the string (for intstance: flip(2576, 2nd power, 2nd position) = 2376, i.e. 3 = 8-5).
I do understand that in octal representation the any similar formulas as for rotate_left or flip are not possible (maybe?), that is why I look for alternative implementation. A possibility would be to represent each number in the octal string by their binary string, in other words to write: 29 --octal-> 35 --bin-> (011)(101) Thus working on sets of binary numbers. Would that be a good idea?
If you have any suggestions for the code above for binary representation, I welcome any piece of advice.
Thanks in advance and sorry for the long post!
my understand of rotate_left, do not know my understand of question is correct, hope this will help you.
// 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);
}
flip, for base 8, flip should be 7-x instead of 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;
}
simple reverse.
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;
}