Bitwise Tricks

C codeDescriptionObtained from
a ^= b; b ^= a; a ^= b;Swap a and b aroundComputerShopper
c & -c or c & (~c + 1)return first bit setEivind Eklund
~c & (c + 1)return first unset bitEivind Eklund
unsigned i, c = <number>;
for (i = 0; c; i++) c ^= c & -c;
i will contain the number of bits set in cEivind Eklund
m = (m & 0x55555555) + ((m & 0xaaaaaaaa) >> 1);
m = (m & 0x33333333) + ((m & 0xcccccccc) >> 2);
m = (m & 0x0f0f0f0f) + ((m & 0xf0f0f0f0) >> 4);
m = (m & 0x00ff00ff) + ((m & 0xff00ff00) >> 8);
m = (m & 0x0000ffff) + ((m & 0xffff0000) >> 16);
m will now contain number of bits set in the original mpopcnt in FreeBSD's sys/i386/i386/mp_machdep.c
v -= ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = (v + (v >> 4)) & 0x0F0F0F0F;
v = (v * 0x01010101) >> 24;
v will now contain number of bits set in the original vpopcnt comment in FreeBSD's sys/i386/i386/mp_machdep.c
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777) \
- (((x)>>2)&0x33333333) \
- (((x)>>3)&0x11111111))
macro to return number of bits in x (assumes 32bit integer)BSD fortune
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
reverse bits in a 32bit integerBSD fortune
popcnt(x ^ (x - 1)) & 31return first bit set in x, where popcnt returns number of bits setPeter Wemm
ffs using a lookup tablereturn first bit setColin Percival

If you have any other cool bitwise tricks you know about, please e-mail them to John-Mark Gurney <jmg@funkthat.com>, and I will add them to the list.

A large collection of them can be found at Bit Twiddling Hacks.



email jmg@funkthat.com
Copyright © 1999-2003 by John-Mark Gurney.
All Rights Reserved.