Truncate binary number [duplicate]

Question

I would like to truncate every digit after the first non zero digit in the binary representation of an integer. I also need this to be as simple as possible (no function or multiple lines of code).

In example:

// in c++
int int1=7,int2=12,int3=34;   //needs to work for any number

using some sort of operator (maybe bitwise combination?), I need these to give the following values

int1 -> 4
int2 -> 8
int3 -> 32

Truncating in binary was the only thing I could think of, so I am open to any ideas.

Thanks!

Answer 1

A pretty neat trick can be used for that:

if ((v & (v - 1)) == 0) {
    return v;
}
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;
return v;

The idea is to "OR in" all ones below the top one after decrementing the value, and then increment the value back at the end. I added a shift right at the end to the standard trick, because the original code was designed to find the smallest 2^n greater than or equal to the given value.

EDIT: I also added a special case for 2^N, which is another trick from the same list.

Here is a demo on ideone.

Answer 2

This function is from the book Hacker's Delight.

// greatest power of 2 less than or equal to n (floor pow2)

uint32_t flp2(uint32_t n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n - (n >> 1);
}

And I might as well post the related clp2 function:

// least power of 2 greater than or equal to n (ceiling pow2)

uint32_t clp2(uint32_t n)
{
    n -= 1; 
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}