2

Question: How to develop algorithm to shift all set bits (1) in 32-bits integer to the right

Example 

V= 0b01001000110010

The V contains 5 set bits and if we shift them to the right we get:

V = 0b011111

What I have tried:

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

The above code return the number of set bits in 32-bits integer

and with the following code

c = (1<<c) - 1;

we will get the c first bits set to 1. Explaination

Are there other algorithmes better than the above solution?

Is it possible to use only bitwise operations (&,|, ^, ~, >>, <<) in the proposed solutions?

Community
  • 1
  • 1
MOHAMED
  • 41,599
  • 58
  • 163
  • 268

8 Answers8

7
bitset<32> const bv( V );
size_t const numSetBits = bv.count();
uint32_t const answer = ~( ~0U << numSetBits );
Arun
  • 19,750
  • 10
  • 51
  • 60
  • 1
    This is a good general solution. OP can look at the implementation of `bitset::count` in his standard library if he’s curious. Aside: you might as well make the `bitset` constant, if `count()` is all you’re using it for. I think `(1 << numSetBits) - 1` is clearer, as well. – Jon Purdy Apr 14 '13 at 21:11
  • Note that this fails if the input has all bits set (shifting by such a large amount is undefined behavior). – Marc Glisse Apr 14 '13 at 22:15
  • @MarcGlisse Could you explain more why it's undefined behaviour – MOHAMED Apr 14 '13 at 22:16
  • Because it says so in the standard (because some processors will replace a< – Marc Glisse Apr 14 '13 at 22:17
  • @MOHAMED: Thanks. Marc Glisse: Can you provide some reference about the undefined behavior situation? – Arun Apr 15 '13 at 04:11
  • @Arun Well it's obviously somewhere in the standard (shouldn't be hard to find, but I don't have my standard with me). But it's not very surprising: Shifting 32+ bits in a 32bit data type doesn't make a lot of sense and different ISAs handle this situation differently (eg x86 vs. x64 can give different results if you do the computation in 64bit words and then only write the lower word out; x86 only uses the lower 5 bits). In the end the fix is trivial and may even be free: `(1 << (numSetBits % wordSize)) - 1` will work correctly in all cases as long as its unsigned. – Voo Apr 15 '13 at 07:04
4

The best solution that I see is to use the population count to get the number of 1 bits and then just use (1 << (pop_cnt % typeSize)) - 1[1], which is what you're already doing.

To find the population count you can look here, there are several efficient implementations. If you are fine with gcc there is gcc's builtin __builtin_popcount instruction which should generate the most efficient code for your hardware.

[1] As was correctly pointed out in the comments for another post 1 << pop_cnt is undefined behavior if all bits are set to one in the word. To avoid this apply modulo wordsize beforehand. As long as you're using an unsigned type this will avoid undefined behavior, give you the correct results and should actually produce exactly the same code under x86 if you use wordsized data types.

Voo
  • 29,040
  • 11
  • 82
  • 156
0

You could use V >>= 1; or int v = (V >> 1); could you not?

If the intent is to shift all non-zero bits to all the way to the right, then you could do it like this...

int v = 0;
int i;

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

V = v;
K Scott Piel
  • 4,320
  • 14
  • 19
0

You could try to find a magic constant and use multiplication and a shift-right with (32 - 5) (assuming you use 32-bits integers to store the constants).

#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
}

Look at this question on how to find such constants

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • V is not constant . I m looking for common algorithme. the input is v and the output is the set bits shifted to the right – MOHAMED Apr 14 '13 at 21:07
  • @MOHAMED OK, then the solution by Arun Saha is what you can use. I'll leave this answer for future reference for people who need constant V. – TemplateRex Apr 14 '13 at 21:17
0

This will do it for some value 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;
Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
0

I suggest using two variables: 

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;
}

Although this function doesn't count bits, it does resolve your example.

This would be better implemented in assembly language, because you could shift the bit into carry, then shift carry into the result.

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154
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;
Alexander Shukaev
  • 16,674
  • 8
  • 70
  • 85
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;
}

Saves some additions.

TNW
  • 716
  • 6
  • 15