C - Bit Twiddling
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);