将n个连续位设置为1的最有效方法是什么？

Question

我想得到一个函数,将n数值类型的最后几位设置为1.例如:

bitmask (5) = 0b11111 = 31
bitmask (0) = 0

我,第一,有此实现(mask_t只是typedef周围uint64_t):

mask_t bitmask (unsigned short n) {
  return ((((mask_t) 1) << n) - 1;
}

一切都很好,除非函数命中bitmask (64)(大小mask_t),然后我得到bitmask (64) = 064位设置为1.

所以,我有两个问题:

1. 为什么我有这种行为？按下1左侧的64个移位应该清除寄存器并保持0,然后应用-1应该用1s 填充寄存器...

2. 实现此功能的正确方法是什么？

Answer 1

是的,这是一个众所周知的问题.有很多简单的方法可以在0..63范围内和1..64范围内实现此功能(注释中已经提到了一种方法),但0..64更难.

当然你可以采取"左移"或"右移"掩模生成,然后特殊情况下"缺失" n,

uint64_t bitmask (unsigned short n) {
  if (n == 64) return -((uint64_t)1);
  return (((uint64_t) 1) << n) - 1;
}

要么

uint64_t bitmask (unsigned short n) {
  if (n == 0) return 0;
  uint64_t full = ~(uint64_t)0;
  return full >> (64 - n);
}

无论哪种方式趋于编译为一个分支,虽然它在技术上并不具备对.

没有if(未经测试)你可以做到

uint64_t bitmask (unsigned int n) {
  uint64_t x = (n ^ 64) >> 6;
  return (x << (n & 63)) - 1;
}

这里的想法是,我们要么向左移动一些与原始代码相同的数量,或者在这种情况下为0 n = 64.将0向左移0再次为0,减去1组全部为64位.

或者,如果您使用的是现代x64平台且BZHI可用,则速度非常快(BZHI在所有实现它的CPU上都很快),但有限的便携性选项是:

uint64_t bitmask (unsigned int n) {
  return _bzhi_u64(~(uint64_t)0, n);
}

这甚至是明确定义的n > 64,1的实际计数将是min(n & 0xFF, 64)因为BZHI饱和但它只读取索引的最低字节.