Truncate binary number

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!

Every way I know to do this involves multiple lines of code. Are you sure you can't handle a function call wherever you are going to be using this? — Patricia Shanahan, Jul 22 '13 at 01:17
@PatriciaShanahan I am doing a triple integration, so no. But I think I may look into storing the values I need beforehand. — Couchy, Jul 22 '13 at 01:32

Sergey Kalinichenko · Accepted Answer · 2013-07-22T01:19:05.840

3

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.

edited Jul 22 '13 at 01:19

answered Jul 22 '13 at 01:08

Sergey Kalinichenko

714,442
84
1,110
1,523

I think you need to adjust for the case of an exact power of 2. I got 16 running your code for input 32. Maybe keep the original value of v as old_v, and if the value of v after v++ is equal to old_v, don't do the final shift. – Patricia Shanahan Jul 22 '13 at 01:15
@PatriciaShanahan Thanks for the note, I added a work-around for this special case. – Sergey Kalinichenko Jul 22 '13 at 01:20
Thanks, I am not that good with bitwise operators, but I am assuming that this checks all possible cases, thus would require more checks for anything higher than 31 (right?). For my purpose, I need to assume that the maximum number is 2^15, so I am afraid that doing so would dramatically slow down the process, which I cannot afford (approximating an integral). – Couchy Jul 22 '13 at 01:24
@user1888743 There are no additional checks that you would need to perform. This trick works for all values of v within the range, assuming that v is unsigned. – Sergey Kalinichenko Jul 22 '13 at 01:37
@dasblinkenlight How would you implement this in a `#define` statement in such a way that you could use it as a single value? – Couchy Jul 22 '13 at 03:01
1

@user1888743 Why, wouldn't an inlineable C99 function work? Macro would be incredibly ugly... – Sergey Kalinichenko Jul 22 '13 at 03:05

Blastfurnace · Answer 2 · 2013-07-22T01:26:33.820

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

Truncate binary number

2 Answers2