将n个连续位设置为1的最有效方法? [英] Most efficient way to set n consecutive bits to 1?

问题描述

我想获得一个将数字类型的n最后一位设置为1的函数.例如:

I want to get a function that will set the n last bits of a numerical type to 1. For example:

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

我首先实现了此实现(mask_t只是uint64_t周围的typedef):

I, first, had this implementation (mask_t is just a typedef around uint64_t):

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

一切都很好，但是当函数按bitmask (64)(mask_t的大小)时，我得到了bitmask (64) = 0，而不是设置为1的64位.

Everything is fine except when the function hit bitmask (64) (the size of mask_t), then I get bitmask (64) = 0 in place of 64 bits set to 1.

所以，我有两个问题:

1. 为什么会有这种行为?将1向左推64档应清除寄存器并保留0，然后应用-1则应将1 s ...

1. Why do I have this behavior ? Pushing the 1 by 64 shifts on the left should clear the register and remain with 0, then applying the -1 should fill the register with 1s...

实现此功能的正确方法是什么?

What is the proper way to achieve this function ?

推荐答案

是的，这是一个众所周知的问题.在0..63范围和1..64范围内(有一种方法已经在注释中提到)，有很容易的方法来实现此功能，但是0..64更加困难.

Yes this is a well known problem. There are easy ways to implement this function over the range 0..63 and over the range 1..64 (one way has been mentioned in the comments), but 0..64 is more difficult.

当然，您可以仅生成左移"或右移"蒙版，然后对缺失" n进行特殊处理，

Of course you can just take either the "left shifting" or "right shifting" mask generation and then special-case the "missing" 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);
}

这两种方法都倾向于编译为分支，尽管从技术上讲它不是必须.

Either way tends to compile to a branch, though it technically doesn't have to.

您可以在没有if的情况下进行此操作(未经测试)

You can do it without if (not tested)

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

这里的想法是，我们将向左移1到您原始代码中的某个量，或者向左移n = 64.将0左移0只是将再次变为0，减去1将设置所有64位.

The idea here is that we're going to either shift 1 left by some amount the same as in your original code, or 0 in the case that n = 64. Shifting 0 left by 0 is just going to be 0 again, subtracting 1 sets all 64 bits.

或者，如果您使用的是现代x64平台，并且BZHI可用，则速度非常快(BZHI在实现该功能的所有CPU上都是快速的)，但是可移植性有限的选项是:

Alternatively if you're on a modern x64 platform and BZHI is available, a very fast (BZHI is fast on all CPUs that implement it) but limited-portability option is:

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

对于n > 64来说，这甚至是定义明确的，由于BZHI饱和，但实际的1计数为min(n & 0xFF, 64).

This is even well-defined for n > 64, the actual count of 1's will be min(n & 0xFF, 64) because BZHI saturates but it reads only the lowest byte of the index.

这篇关于将n个连续位设置为1的最有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！