CODEWITHSUNDEEP
c++cbit-manipulation
MOHAMED
MOHAMED

Reputation: 43518

How to move all set bits to the right?

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?

Upvotes: 2

Views: 3468

Answers (8)

Voo
Voo

Reputation: 30216

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.

Upvotes: 4

TNW
TNW

Reputation: 726

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.

Upvotes: 0

TemplateRex
TemplateRex

Reputation: 70526

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

Upvotes: 0

Arun
Arun

Reputation: 20383

bitset<32> const bv( V );
size_t const numSetBits = bv.count();
uint32_t const answer = ~( ~0U << numSetBits );

Upvotes: 7

Alexander Shukaev
Alexander Shukaev

Reputation: 17021

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;

Upvotes: 0

Thomas Matthews
Thomas Matthews

Reputation: 57698

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.

Upvotes: 0

Drew Dormann
Drew Dormann

Reputation: 63775

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;

Upvotes: 0

K Scott Piel
K Scott Piel

Reputation: 4380

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;

Upvotes: 0

Related Questions