ruk·si

🔹 C
Bit Twiddling

Updated at 2013-11-12 00:07

Bit twiddling is the manipulation of bits. Bit manipulation is usually required for low-level device control, error detection and various algorithms. It is rarely required on the modern programming languages except for performance.

If not state otherwise, constant CHAR_BIT in the following examples is the number of bits in a byte of the runtime environment, almost always 8. The value can be included from limits.h in C.

#include <stdio.h>
#include <limits.h>

int main()
{
    printf("%d\n", CHAR_BIT); // => 8
}

Some basics bit operations.

printf("%#010x\n", 0x0F);        // 0x0000000F
printf("%#010x\n", ~0x0F);       // 0xFFFFFFF0 - Negation
printf("%#010x\n", 0x0F & 0xF0); // 0x00000000 - AND
printf("%#010x\n", 0x0F | 0xF0); // 0x000000FF - OR
printf("%#010x\n", 0x04 ^ 0x0F); // 0x0000000B - XOR
printf("%#010x\n", 0x04 << 1);   // 0x00000008 - Bitwise Shift Left 1
printf("%#010x\n", 0x04 >> 1);   // 0x00000002 - Bitwise Shift Right 1

Check the sign of an integer.

int xxx = -1;

int sign = -(xxx < 0);
printf(sign ? "Has sign." : "Does not have sign.");
// -1 for negative, 0 for zero and positive.

int pos_neg_zero = (xxx > 0) - (xxx < 0);
// -1 for negative, 0 for zero, 1 for positive.

Check if two integers have opposite signs.

int x = 1;
int y = -1;
int opposite = ((x ^ y) < 0);
printf(opposite ? "Have opposite signs." : "Have the same sign.");

Compute integer absolute value.

int xxx = -154;
unsigned int absolute = (xxx < 0) ? -(unsigned)xxx : xxx;
printf("%d", absolute);

Compute integer absolute value without branching.

int xxx = -154;
int const CHAR_BIT = 8;
int const mask = xxx >> sizeof(int) * CHAR_BIT - 1;
unsigned int absolute = (xxx + mask) ^ mask;
printf("%d", absolute);

Compute minimum or maximum of two integers.

int x = -5;
int y = 1;
int min = (x < y) ? x : y;
int max = (x > y) ? x : y;
printf("Min: %d Max: %d", min, max);

Compute minimum or maximum of two integers without branching.

int x = -5;
int y = 1;
int min = y ^ ((x ^ y) & -(x < y));
int max = x ^ ((x ^ y) & -(x < y));
printf("Min: %d Max: %d", min, max);

Check if an integer is a power of two.

unsigned int xxx = 16;
int is_power_of_two = xxx && !(xxx & (xxx - 1));
printf(is_power_of_two ? "Is power of two." : "Not power of two.");

Conditionally negate a value.

bool doNegate = true;
int xxx = 1213;
int result = (xxx ^ - doNegate) + doNegate;
printf("%d", result);

// Alternative
bool doNotNegate = false;
int xxx = 1213;
int result = (doNotNegate ^ (doNotNegate - 1)) * xxx;
printf("%d", result);

Merge bits from two values using a mask.

// mask: 0 = take from a, 1 = take from b
unsigned int a = 6;     // a = 0110
unsigned int b = 8;     // b = 1000
unsigned int mask = 2;  // m = aaba
unsigned int result = a ^ ((a ^ b) & mask);
printf("%d", result);   // r = 0100 = 4

Count number of bit sets, the ones in the binary.

unsigned int xxx = 13; // 1101
unsigned int count;
for (count = 0; xxx; count++)
{
    xxx &= xxx - 1;
}
printf("%d", count); // => 3

Counting parity bit, used for error detecting.. Parity bit is 1 if count of ones in given value is odd. Parity bit is 0 if count of ones in given value is even.

unsigned int xxx = 7; // 111
bool parity = false;
while (xxx)
{
    parity = !parity;
    xxx = xxx & (xxx - 1);
}
printf("%d", parity);

Swapping two values without using extra space for a temporary variable.

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
unsigned int x = 2;
unsigned int y = 10;
SWAP(x, y);
printf("x: %d y: %d", x, y);

Sources