News for hackers. Stuff that matters.
Re:Ten Ways to Check if an Integer Is a Power Of Two in C by gjm11 on Tuesday July 26, 2011 @06:16PM (#2809713)
Here's another. It's strictly inferior to the x&(x-1) one, but the idea that makes it work is so pretty it seems worth mentioning.

  y = x | (x>>1);
  y |= y>>2;
  y |= y>>4;
  y |= y>>8;
  y |= y>>16;
  y |= y>>32; // for 64-bit numbers;
  return y == (x<<1)-1;
So what's going on here? Well, it's easy enough to locate the lowest set bit in x -- it's x & -x, the same basic idea as the x&(x-1) trick -- but what the code above does is to locate the highest by "filling" rightwards from that bit. After the first line, the 1-bits in y are the 1-bits in x, and the bits one to the right of them. After the second, it's the 1-bits in x shifted right by 0..3 places. After the next, 0..7 places. And so on. Eventually, that comes to "all the 1-bits in x, and everything any distance to their right". So, e.g., 000101000100 -> 000111100110 --> 000111111111 which then doesn't change.

The nice thing is that the number of steps this takes goes like log(word width). It's in the same spirit as the 0x33333333 popcount trick.

(On some processors -- all x86 ones since 386, for instance -- there's an instruction that does something similar directly, but on at least some x86 processors it's rather slow.)

There are no comments on this comment yet.