gcc有一个高效的位操作指令__builtin_ctz,它可以O(1)的时间代价获取8字节整数低位连续0的个数,比如:
__builtin_ctz(1)= 0, (1)
__builtin_ctz(2) = 1, (10)
__builtin_ctz(4) = 2, (100)
__builtin_ctz(6) = 1, (110)请基于该指令实现一个高效的bitset,该bitset最大支持512位,这里需要实现两个函数:
- void set_bit(int index); 将指定bit位置1
- int find_first(int from); 从右往左,即返回低from位开始的第一个非0位的索引
答案:
#include <stdio.h>
#include <stdint.h>
// 定义 bitset 结构
typedef struct
{
unsigned long long bits[8];
}BitSet;
void printBitSet(BitSet* bs)
{
for(int i = 7; i >= 0; --i)
{
printf("%llu ", bs->bits[i]);
}
printf("\n");
}
void set_bit(BitSet* bs, int index)
{
if(index < 512)
{
bs->bits[index / 64] |= 1ULL << (index % 64);
}
}
int find_first(BitSet* bs, int from)
{
for(int i = from / 64; i < 8; ++i)
{
// 生成一个低 (from % 64) 位均为0的掩码
unsigned long long mask = (~(1ULL << (from % 64)) - 1);
if(i != from / 64)
{//掩码只在首次循环时需要
mask = ~0;
}
if((bs->bits[i] & mask) != 0)
{
return i * 64 + __builtin_ctz(bs->bits[i] & mask);
}
}
return -1;//没有
}
int main() {
BitSet bs = {{0}}; // 初始化为全0
set_bit(&bs, 0);
printBitSet(&bs);
set_bit(&bs, 64);
printBitSet(&bs);
int first = find_first(&bs, 0);
printf("First non-zero bit: %d\n", first);
first = find_first(&bs, 1);
printf("First non-zero bit: %d\n", first);
return 0;
}
输出结果是:
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
First non-zero bit: 0
First non-zero bit: 64
注:1ULL 的含义是将整数1显式地标记为 64 位的无符号 long long 类型。这样做是为了确保该整数字面量被作为 64 位无符号整数来处理。
类似的写法还有:
1UL // 无符号 long 类型
1U // 无符号 int 类型
1L // long 类型
这些写法可以用于显式指定整数字面量的数据类型,以确保在进行表达式计算时使用指定的数据类型。