Bitwise Operations (Part-1)

ALL_BITS:

Getting an integer with all bits set. Following expression will provide us an integer of 31 bits where all bits set. Maximum positive integer of **int** data type.

(1 << 31) - 1

#define ALL_BITS                 ((1 << 31) - 1)
NEG_BITS:

Given an integer N, generate a new integer where all bits are toggled. Example: Negetion of 101 will be 010.

(N ^ ALL_BITS)

#define NEG_BITS(N)             (N ^= ALL_BITS)
TEST_BIT:

Given an integer N, check is i'th bit is set or not.

N & (1 << i)

#define TEST_BIT(N, i)          (N & (1 << i))
ON_BIT:

Given an integer N, turn on a specific bit.

N | (1 << i)

#define ON_BIT(N, i)                (N |= (1 << i))
OFF_BIT:

Given an integer N, turn off a specific bit.

(N & NEG_BITS(1 << i)

#define OFF_BIT(N, i)           (N &= NEG_BITS(1 << i))
TOGGLE_BIT:

Given an integer N, turn off a specific bit.

N ^ (1 << i)

#define TOGGLE_BIT(N, i)            (N ^= (1 << i))
IS_POWER_TWO:

Given an integer N, check is it power of 2. There are several ways to do this.

N && !(N & (N - 1)) (N & -N) == N N & (N - 1)

#define IS_POWER_TWO(N)             (N && !(N & (N-1)))
#define IS_POWER_TWO(N)             ((N & -N) == N)
#define IS_POWER_TWO(N)             (N & (N - 1))
OFF_LOWEST_SET_BIT

Given an integer N, turn off lowest set bit.

(N & (N - 1))

#define OFF_LOWEST_SET_BIT(N)          (N &= (N - 1))
LOWEST_SET_BIT_POSITION

Given an integer N, get the position of lowest set bit.

N ^ (N & (N - 1))

#define LOWEST_SET_BIT_POSITION(N)      (N ^ (N & (N - 1)))
DEVIDE_BY_POWER_TWO

Given an integer N and P where N is need to be devided by P and P is an integer which is power of 2, then we can perform the division using bitwise operation.

N & (P - 1)

#define DIVIDE_BY_POWER_TWO(N)            (N & (P - 1))
Useful methods related to bitwise operation in C/C++:
// Count trailing zeros
__builtin_ctz(int N);

// Count leading zeros
__builtin_clz(int N);

// How many bits are set
__builtin_popcount(int N);
Blog Comments powered by Disqus.

Next Post Previous Post