一些位运算技巧

一、整数乘(除)以2的幂

a = 1;
a <<= 1;//右移几位即为乘以2的几次方,a乘以2,此时a为2
a <<= 3;//a乘以8(2^3),此时a为16
a = 27;
a >>= 2;//左移几位即为除以2的几次方,a除以4,此时a为6

二、掩码

以64位掩码为例:

#include <stdio.h>

int main() {
    unsigned long long mask_code = 0xFFFFFFFFFFFFFFFFull << 32;//高32位的掩码
    unsigned long long num = 0xAAAAAAAAAAAAAAAAull;
    printf("%llX", mask_code & num);//AAAAAAAA00000000
}

三、交换两整型

可以不借助第三个临时变量来交换两整型,也不会像加减交换有溢出的可能

int a = 22, c = 33;
//a ^= b ^= a ^= b;//可以写成一行 c/c++结果正常 jdk8其中一个数会赋为0 应该像下面这样写
a ^= b;
b ^= a;
a ^= b;

四、交叉取位

//方法1
unsigned int a = 0xffffffff, b = 0;
unsigned long long c = 0;
for(int i = 0; i < 32; i++)
    c |= ((a & (1ull) << i) << i) | ((b & (1ull) << i) << (i + 1));

//方法2
c = ((unsigned long long)(b) << 32) | c;
c = (c & 0x9999999999999999ull) | ((c & 0x4444444444444444ull) >>  1) | ((c & 0x2222222222222222ull) <<  1);
c = (c & 0xA5A5A5A5A5A5A5A5ull) | ((c & 0x5050505050505050ull) >>  3) | ((c & 0x0A0A0A0A0A0A0A0Aull) <<  3);
c = (c & 0xAA55AA55AA55AA55ull) | ((c & 0x5500550055005500ull) >>  7) | ((c & 0x00AA00AA00AA00AAull) <<  7);
c = (c & 0xAAAA5555AAAA5555ull) | ((c & 0x5555000055550000ull) >> 15) | ((c & 0x0000AAAA0000AAAAull) << 15);
c = (c & 0xAAAAAAAA55555555ull) | ((c & 0x5555555500000000ull) >> 31) | ((c & 0x00000000AAAAAAAAull) << 31);

五、取最高位的1

//32位
unsigned int m = 0x1234;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m = (m + 1) >> 1;

六、取最低尾的1

//64位
unsigned long long g = 0x12345678;
cout << bitset<64>(g) << endl;
g = g&-g;//g=g&(~g+1)
cout << bitset<64>(g) << endl;
输出

七、末尾零的个数

结合第一点和第六点及德布鲁因序列在O(1)时间内求解。德布鲁因序列按顺序取固定位,结果两两不同:

德布鲁因序列及其子序列

生成查找表:

const static unsigned long long n = 0x218A392CD3D5DBF;
int table[64];
for(int i = 0; i < 64; i++)
    table[(n << i) >> 58] = i;

对任意64位x,以i为最低位的位数(0开始),n为德布鲁因序列。取最低位的1为(x&-x),等于(2^i),再乘以n,即表示n左移最低位1的位数。则以下两式等价(i表示n最低位的位数):

((x&-x)*n) ⇔ (x&(~x+1)) ⇔ (n*2^i) ⇔ (n<<i)

int count_trailing_zeros1(unsigned long long x) {
    const static unsigned long long n = 0x218A392CD3D5DBF;
    const static int table[] = {0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47,
                                30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58};
    return x != 0 ? table[((x & -x) * n >> 58)] : 64;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注