More Bit-twiddling

This week, two “quickies”: rounding up and down to the next power of two, and converting efficiently a value to exactly 0 or 1.

The need to round up or down a value to a given power of two, say 2^n, happens once in a while. This is rather easy, it suffice to compute (x+2^n-1) \wedge_\mathbb{B} \neg_\mathbb{B}(2^n-1), where \wedge_\mathbb{B} and \neg_\mathbb{B} are, respectively, the bitwise and and the bitwise negation. In C, the expression becomes:

const int next_power=(1<<n)-1;
...
x=(x+next_power) & ~next_power;
&#91;/sourcecode&#93;<br><br>

To truncate, the expression becomes x \wedge_\mathbb{B} \neg_\mathbb{B}(2^n-1). It yields the following C code:<br><br>


x &= ~next_power; // sets the last n bits to 0

To round, we would have (x+2^{n-1}) \wedge_\mathbb{B} \neg_\mathbb{B}(2^n-1), yielding:

const int half_power=1<<(n-1); // not with -1
...
x=(x+half_next_power) & ~next_power;
&#91;/sourcecode&#93;<br><br>

Indeed, testing all those:<br><br>


#include <stdio.h>

int main()
 {
  const int next_power=(1<<3)-1;
  const int half_next_power=(1<<2);

  int x=6;

  printf(" rounding up: %d\n"
         " rounding down: %d\n"
         " rounding : %d\n",
         (x+next_power) & ~next_power,
         x & ~next_power,
         (x+half_next_power) & ~next_power);


  return 0;
 }
&#91;/sourcecode&#93;<br><br>

yields the expected result:<br><br>


> a.out
 rounding up: 8
 rounding down: 0
 rounding : 8

Converting a value to exactly 0 if it is zero and exactly 1 otherwise is not very complicated, provided you have the type bool at hand. In C++ and C99, bool is natively supported, and it suffice to cast the value as bool, say (bool)x for C-style casts or static_cast<bool>(x) for the C++ “new style” cast.

In ANSI C, however, there’s no such thing as bool, and meager #defines will not help you convert a value to exactly 0 or 1 as the compiler doesn’t know how to do that. One possible solution is to use comparison operators:

bit = (x!=0); // will yield exactly 0 or 1

If you rather want to promote any value other than zero to 0xff...f, you can use:

mask = -(x!=0); // will yield exactly 0 or 0xff...f

The sex function I presented earlier and also be of some use:

mask = sex(x|-x);

Which yields the same result.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: