Bit manipulation

Basics

Hexadecimal Conversion (十六進位)

Hexadecimal numbers uses 16 values to represent a number. (4個一數) Numbers from 0-9 are expressed by digits 0-9 and 10-15 are represented by characters from A – F.

Example: 0101 = 5 1010 = A 1010 1010 1010 1010 1010 1010 1010 1010 = 0x

Signed & Unsigned Representation

Signed: Allows both negative and positive numbers. The first bit represents the sign (0 for non-negative, 1 for negative), and the remaining bits represent the magnitude of the number. Two’s complement is commonly used.

Unsigned: Only allows non-negative numbers. The entire bit range represents the magnitude of the number.

Range

Signed: $-2^{(n-1)} \text{ to } 2^{(n-1)} - 1 = 10000000 \text{ to } 0111111111$
Unsigned: $0 \text{ to } 2^n - 1$

Overflow

If a number exceeds the upper bound of its representation, it overflows. In signed representation, the next number after the maximum positive value is the minimum negative value, while in unsigned representation, it wraps around to 0.

Operations

Operators	Operations	Result
XOR	X ^ 0s	X
XOR	X ^ 1s	~X
XOR	X ^ X	0
AND	X & 0s	0
AND	X & 1s	X
AND	X & X	X
OR	X \| 0s	X
OR	X \| 1s	1s
OR	X \| X	X

Magic Operations

// XNOR = ~(a ^ b)

// 最后一位取反(101101->101100)                                
x ^ 1

// 取末k位(1101101->1101,k=5)
x & ((1 << k)-1)

// 末k位取反(101001->100110,k=4)                        
x ^ ((1 << k)-1)

// 把右边连续的1变成0(100101111->100100000)               
x & (x+1)

// 把右边连续的0变成1(11011000->11011111)
x | (x-1)

// 取右边连续的1(100101111->1111)                        
(x^(x+1)) >> 1

// 去掉右起第一个1的左边(100101000->1000,树状数组)
x & (x ^ (x-1))

Untitled

Basic bit operation functions

// Get bit
boolean getBit(int i, int num){
     return ( (num & (1 << i)) != 0 ) 
}
// Set bit (set i to 1)
int setBit(int i, int num){
		return num | (1 << i);
}

// Update
int upateBit(int num, int i, Boolean bitIs1){
    int mast = ~(1 << i)
		return (num & mask) | (bitIs1 << i); 
}

// Clear bit
int clearBit(int num, int i) {
		int mast = ~(1 << i);
		return num & mask;
}

Switch a and b

a -= b, b += a, a = b - a
a ^= b, b ^= a, a ^= b

Big Little endian

Big-endian: The most-significant byte of a word is stored at lower memory addresses. Little-endian: The most-significant byte of a word is stored at higher memory addresses.

Quiz: To check is big endian, assign with 00000001 00000010. If

bool IsBigEndian()
{
    union
    {
        unsigned short a ;
        char b ; // c.b represents the first byte of the memory location occupied by the union member c
    } c;


    c.a =0x0102 ;
    
	if(c.b == 1) // The first byte (c.b) is 00000001, which is 1
        return true ;
    else
        return false ;
}

Quiz: How to check if a number is power of 2

int main(void){
	if (n == 0) return false;
	if( (n & (n-1)) == 0) return true;
	else return false;
}

Quiz: RGB 16 bits to 32 bits RGBX

/* from rrrr rggg gggb bbbb */
unsigned long r = (a & 0xF800) >11;
unsigned long g = (a & 0x07E0) >5;
unsigned long b = (a & 0x001F);

/* 2. Convert them to 0-255 range:
There is more than one way. You can just shift them left:
to 00000000 rrrrr000 gggggg00 bbbbb000
r <<= 3;
g <<= 2;
b <<= 3;
But that means your image will be slightly dark and
off-colour as white 0xFFFF will convert to F8,FC,F8
So instead you can scale by multiply and divide: */

r = r * 255 / 31;
g = g * 255 / 63;
b = b * 255 / 31;
/* This ensures 31/31 converts to 255/255 */

/* 3. Construct your 32-bit format (this is 0RGB): */
return (r << 16) | (g << 8) | b;

/* Or for BGR0:
return (r << 8) | (g << 16) | (b << 24);
*/
/* Or for RGBX:
return (r<<24) | (g<<16) | (b<<8)
*/

Practice & Leetcode

There is an unsigned integer n, and we want to swap the value in position 0 with 1, position 2 with 3, and so on and so forth.

a = (n>>1) & 0x55555555
b = (n<<1) & 0xAAAAAAAA
res = a & b

Hamming Distance
Total Hamming Distance

Resources

Standford bit minipulation
Geeksforgeeks