Bitwise Operations

Programmers write code in a high level language and the compiler converts it into assembly code and the assembler converts it into machine code
Programming languages are byte-oriented but hardware is bit-oriented
C provides 6 bitwise operations for bit manipulation
Bitwise operations cannot be used on floats and doubles
When bitwise operators are applied on ints and chars the number is converted to a binary number for operations

$$ \text{AND: &} $$ $$ \text{OR: |} $$ $$ \text{XOR: ^} $$ $$ \text{Complement: ~} $$ $$ \text{Left Shift: <<} $$ $$ \text{Right Shift: >>} $$

Bitwise Operations: AND (&)

The & operator is a binary operator so it requires 2 operands

$$ \text{Rules for & Operator } $$ $$ \text{0 & 0 = 0} $$ $$ \text{0 & 1 = 0}$$ $$ \text{1 & 0 = 0}$$ $$ \text{1 & 1 = 1}$$

Used to turn off a bit when & with 0

$$\text{Binary Value of 12 } \rightarrow 0000 \space{} 1100$$ $$\text{AND mask} \rightarrow 1111 \space{} 1011 $$ $$\text{Result} \rightarrow 0000 \space{} 1000 \text{ (3rd bit is now off)}$$

Used to check if a bit in a number is ON (1) or OFF (0)

$$\text{Binary Value of 6 } \rightarrow 0000 \space{} 0110$$ $$\text{AND mask} \rightarrow 0000 \space{} 0100 $$ $$\text{Result is} \rightarrow 0000 \space{} 0100 $$

void checkIf7thBitIsOn(int n)
{
	int result = n & 128;
	
	if (result> 0)
	    printf(" 7th bit of %d  is ON \n" ,n );
	else
	    printf(" 7th bit of %d  is OFF \n" ,n );
}

Used to check if the given number is a power of 2

void checkIfPowerOfTwo(int x)
{
	// Note that (x & (x-1)) works because if x = 100..(p-times) then x-1=1111...((p-1) times)
	int result = (x != 0) && ((x & (x - 1)) == 0);
	if(result > 0)
		printf(" %d is a power of 2 \n" ,x );
	else
		printf(" %d is not a power of 2 \n" ,x );
}

Bitwise Operations: OR (|)

The Bitwise OR operator is also a binary operator so it requires 2 operands.

$$ \text{Rules for | Operator } $$ $$ \text{0 | 0 = 0} $$ $$ \text{0 | 1 = 1}$$ $$ \text{1 | 0 = 1}$$ $$ \text{1 | 1 = 1}$$

Example: consider a = 10 and b = 6. Find a | b

$$ \text{8 bit binary value of a} \rightarrow 0000 1010 $$ $$ \text{8 bit binary value of b} \rightarrow 0000 0110 $$ $$ \text{result of a | b } \rightarrow 0000 1110$$

Used to turn on a bit when OR with 1

If you want to set 3rd bit as 1 in the given number 0000 0111(decimal 7) then the OR
mask = 23 ie 8(0000 1000). This OR mask is OR with original number 0000 0111.

$$ \text{Binary value of 7} \rightarrow 0000 \space{} 0111 $$ $$ \text{OR mask} \rightarrow 0000 \space{} 1000 $$ $$ \text{Result } \rightarrow 0000 \space{} 1111$$

Turning on a particular set of bits is done in a similar way as above except multiple bits are set in the OR mask

char* toBinary(int n)
{
    int len = 32;
    char* binary = (char*)malloc(sizeof(char) * len);
    int k = 0;
    for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
        binary[k++] = (n & i) ? '1' : '0';
    }
    binary[k] = '\0';
    return binary;
}

void turnOnThe3rdBit(int x)
{
	// 0100 => 4 in decimal
	int result = x | 4;
		printf(" Before %d:%s After turning on 3rd bit %d:%s \n" ,x, toBinary(x), result, toBinary(result) );
}

Bitwise Operation: XOR (^)

The XOR operator is a binary operator so it requires 2 operands

Only returns true if only 1 of the operands is 1 (not both (1 ^ 1 = 0)

$$ \text{Rules for ^ Operator } $$ $$ \text{0 ^ 0 = 0} $$ $$ \text{0 ^ 1 = 1}$$ $$ \text{1 ^ 0 = 1}$$ $$ \text{1 ^ 1 = 1}$$

Used to toggle a bit

Given an array find the only number that appears an odd number of times

Swap 2 numbers

Bitwise Operation: One's Complement (~)

The one's complement operator is a unary operator. So it requires only one operand
In one's complement of a number, all 1's present in the number are changed to 0's and all 0's are changed to 0's.

Example:if a =0000 0000(decimal 0) ones complement of a ie ~a= 1111
1111(decimal 255). If a=1111 1111 then ~a=0000 0000.

Used to check if a given number is odd or even

void checkIfGivenNumberIsEven(int x)
{
	int result = !(x &1);
	if(result > 0)
		printf(" %d is even \n" ,x );
	else
		printf(" %d is odd \n" ,x );
}

Bitwise Operation: Left-Shift Operation (<<)

The left shift operator is a binary operator so it requires 2 operands namely left operand and right operand

Left shift operator shifts each bit in the left operand to the left. The number of places the bits are shifted depends on the right operand. So A << 1 would shift all bits in A 1 place to the left.A << 3 shift all bits of A in 3 places to the left.

Used to find all the powers of 2, till a given number k

void findAllPowersOfTwoTillGivenNumber(int x)
{
	int result = 1;
	printf("Printing all powers of 2 till %d", x);
	while( result<= x)
	{
		printf("Next power of 2: %d \n", result);
		result = result << 1;
	}
}

Check if a kth bit is set

Bitwise Operation: Right-Shift Operation (>>)

Shifts bits to the right

The right shift operator is a binary operator so it requires 2 operands namely left
operand and right operand
Right shift operator shifts each left operand to the right. The number of places the
bits are shifted depends on the right operand.
So A >> 1 would shift all bits in A 1 place to the right.A >> 3 shift all bits of A in 3
places to the right.
When the bits are shifted to the right ,blanks are created on the left.These blanks
are always filled with zeros.
Example: if A=65 then binary value of A=0100 0001. A >> 1-->0010 0000 A >>
2-->0000 1000 A >> 3-->0000 0001

Used to divide a number by 2^k