高效位运算

# 位运算的应用

https://graphics.stanford.edu/~seander/bithacks.html

# 高效位运算

__builtin_popcount，__builtin_ffs，__builtin_clz，__builtin_ctz，__builtin_parity都有对应的long和long long版本，只需在函数名后加l或ll即可

# 统计二进制下1的个数

# __builtin_popcount(unsigned int x)函数最优

耗时2.559s

for(int i=(1<<30), j; i>0; i--) j = __builtin_popcount(i);

耗时3.985s

for(int i=(1<<30), j; i>0; i--) j = __builtin_popcountll(i);

# 位运算统计(int) 次优

耗时5.634s

unsigned popcount (unsigned u){
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

for(int i=(1<<30), j; i>0; i--) j = popcount(i);

1
2
3
4
5
6
7
8
9
10

# 删除最低位(int/long long) 最差

耗时40s

int bit_count(int x){
    int ret = 0;
    for(; x; x-=(-x)&x) ret++;
    return ret;
}
for(int i=(1<<30), j; i>0; i--) j = bit_count(i);

1
2
3
4
5
6

# __builtin_ffs(int x) 返回最低位

举个例子：

__builtin_ffs(4+8)=3，因为最低位的4index=3

__builtin_ffs(1)=1

for(int i=(1<<30), j; i>0; i--) j = __builtin_ffs(i); // 1.597s
for(int i=(1<<30), j; i>0; i--) j = log2((-i)&i)+1; // 33.991s

1
2

# __builtin_ctz(unsigned int x) 返回后面0的个数+1

功能等同于__builtin_ffs()

__builtin_ctz(0); // 32 x=0时是未定义的
__builtin_ctz(1); // 1
__builtin_ctz(2); // 2
__builtin_ctz(3); // 1

1
2
3
4

# __builtin_clz(unsigned int x) 返回前导0个数

__builtin_clz(0); // 32 x=0时是未定义的
__builtin_clz(1); // 31
__builtin_clz(2); // 30
__builtin_clz(12); // 28

1
2
3
4

# __builtin_parity(unsigned int x) 奇偶校验返回1的个数余2

__builtin_parity(1); // 1
__builtin_parity(2); // 1
__builtin_parity(3); // 0

1
2
3

上次更新: 2021/02/24, 03:37:30

← 组合情况