64位数据中零半字节的位置查找问题(无循环分支限制)
查找64位数字中唯一零半字节的索引问题
给定一个由16个半字节(4位块)组成的64位数字,已知其中仅有一个半字节为0b0000,需查找其索引(范围0-15)。约束条件为:
- 不能使用迭代、循环或分支语句(if/else)
- 仅可使用位操作
- 允许调用GCC内置函数如
__builtin_ctzll或__builtin_ffsll
我对位操作掌握不足,尝试了如下代码:
x |= x >> 1; x |= x >> 2;
这段代码虽能大致定位目标半字节,但存在大量不符合预期的情况。
此外我参考了相似问题提供的函数,代码如下:
int zero_nibble_position (uint64_t a) { const uint64_t nibble_lsb = 0x1111111111111111ULL; const uint64_t nibble_msb = 0x8888888888888888ULL; uint64_t t = (a - nibble_lsb) & (~a & nibble_msb); return __builtin_clzll(t)/4; }
该函数仅部分输入能正常工作,存在明显错误:例如输入0b0001000000111010010101100111001010010001010011001101111011111011(十进制值为1169342103320059643)时,正确索引应为1,但函数返回0;且当0b0000半字节位于0b0001半字节之后时,索引结果均错误。
内容的提问来源于stack exchange,提问作者Arurikku Burumanto
相关产品推荐
相关产品推荐

