2

问题：如何开发算法将32 位整数1中的所有设置位 ( )向右移动

例子

V= 0b01001000110010

V包含 5 个设置位，如果我们将它们向右移动，我们得到：

V = 0b011111

我试过的：

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

上面的代码以 32 位整数返回设置的位数

并使用以下代码

c = (1<<c) - 1;

我们将第c一个位设置为1. 解释

还有其他算法比上述解决方案更好吗？

在建议的解决方案中是否可以仅使用按位运算（&, |, ^, ~, >>, <<）？

4

8 回答 8

7 
bitset<32> const bv( V );
size_t const numSetBits = bv.count();
uint32_t const answer = ~( ~0U << numSetBits );
于 2013-04-14T21:01:27.623 回答
4

我看到的最佳解决方案是使用人口计数来获得 1 位的数量，然后只使用(1 << (pop_cnt % typeSize)) - 1[1]，这就是您已经在做的事情。

要查找人口计数，您可以查看此处，有几种有效的实现。如果你对 gcc 没问题，那么 gcc 的内置__builtin_popcount指令应该会为你的硬件生成最有效的代码。

[1] 正如另一篇文章的评论中正确指出的那样，1 << pop_cnt如果单词中的所有位都设置为一个，则未定义的行为。为了避免这种情况，请预先应用模字大小。只要您使用无符号类型，这将避免未定义的行为，为您提供正确的结果，并且如果您使用字长数据类型，实际上应该在 x86 下产生完全相同的代码。

于 2013-04-14T21:16:41.720 回答
0 
int v = 0b01001000110010;
int a = 0;

for (int i = 0; i < 32; ++i) {
    if((v & 1) == 1)
       a = (a << 1) + 1;

    v = v >> 1;
}

v = a;
于 2013-04-14T21:05:57.557 回答
0

你可以使用V >>= 1;还是int v = (V >> 1);不可以？

如果目的是将所有非零位一直向右移动，那么你可以这样做......

int v = 0;
int i;

for( i = 0; i < 32; i++, V >>= 1 )
   if( (V & 1) != 0 )
      v = (v << 1) + 1;

V = v;
于 2013-04-14T20:54:36.637 回答
0 
int shift(int V) {
    if (V != 0) {
        int r = 1;
        for (int i = 0; i < 32; i++)
            if ((V >> i) & 1) r <<= 1;
        return r - 1;
    } else return 0;
}

节省一些补充。

于 2013-04-14T21:25:27.270 回答
0

这将获得一些价值v。

// Count the bits (only iterates once per set bit)
unsigned count = 0;
for(; v!=0; v&=(v-1))
    ++count;

// Produce that many "shifted bits".
v = (1 << count) - 1;
于 2013-04-14T21:02:45.050 回答
0

您可以尝试找到一个魔术常数并使用乘法和 (32 - 5) 右移（假设您使用 32 位整数来存储常数）。

#include <iostream>

int main()
{
   unsigned V = 0b01001000110010; 
   unsigned magic = 0x79838cb2; // try some random numbers until you succeed
   unsigned result = (V * magic) >> (32 - 5);   

   std::cout << result; // writes 31
}

看看这个问题如何找到这样的常数

于 2013-04-14T21:00:14.030 回答
0

我建议使用两个变量： 

unsigned int Squish_Bits(unsigned int value)
{
  unsigned int result = 0;
  for (i = 0; i < sizeof(value)/CHAR_BITS; ++i)
  {
    if (value & (1 << i))
    {
       result <<= 1;
       result |= 1;
    }
  }
  return result;
}

尽管此函数不计算位，但它确实解决了您的示例。

这将在汇编语言中更好地实现，因为您可以将位移入进位，然后将进位移入结果。

于 2013-04-14T21:04:18.140 回答