Bit Manipulation Basics

In this page:

Binary Representation
Bitwise Operators
Left Shift
Right Shift
Bit Practice

Binary Representation

Every integer is stored in memory as a sequence of bits, each either 0 or 1, and bitwise operations manipulate those individual bits directly rather than treating the number as a single opaque value the way arithmetic operations do.

Example: Binary Representation

#include <iostream>
#include <bitset>
using namespace std;
int main() {
	int n = 13;
	cout << n << " in binary: " << bitset<8>(n);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 13;
		System.out.println(n + " in binary: " + Integer.toBinaryString(n));
	}
}

n = 13
print(f"{n} in binary: {bin(n)[2:]}")

#include <stdio.h>
int main() {
	int n = 13;
	printf("%d in binary: ", n);
	for (int i = 7; i >= 0; i--) printf("%d", (n >> i) & 1);
	return 0;
}

Bitwise Operators

AND, OR, and XOR compare two numbers bit by bit; NOT flips every bit of a single number; left shift and right shift move all the bits of a number over by a chosen number of positions, filling the vacated spots with zeros.

Example: Bitwise Operators

#include <iostream>
using namespace std;
int main() {
	int a = 12, b = 10;
	cout << "AND=" << (a&b) << " OR=" << (a|b) << " XOR=" << (a^b) << " NOT a=" << (~a);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int a = 12, b = 10;
		System.out.println("AND=" + (a&b) + " OR=" + (a|b) + " XOR=" + (a^b) + " NOT a=" + (~a));
	}
}

a, b = 12, 10
print(f"AND={a&b} OR={a|b} XOR={a^b} NOT a={~a}")

#include <stdio.h>
int main() {
	int a = 12, b = 10;
	printf("AND=%d OR=%d XOR=%d NOT a=%d", a&b, a|b, a^b, ~a);
	return 0;
}

Left Shift

Shifting bits left by k positions inserts k zero bits on the right, which for a positive integer has the same effect as multiplying by 2^k — for example, shifting 3 (binary 011) left by 1 gives 6 (binary 110).

Example: Left Shift

#include <iostream>
using namespace std;
int main() {
	int n = 3;
	cout << n << " << 1 = " << (n << 1) << " (same as multiplying by 2)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 3;
		System.out.println(n + " << 1 = " + (n << 1) + " (same as multiplying by 2)");
	}
}

n = 3
print(f"{n} << 1 = {n << 1} (same as multiplying by 2)")

#include <stdio.h>
int main() {
	int n = 3;
	printf("%d << 1 = %d (same as multiplying by 2)", n, n << 1);
	return 0;
}

Right Shift

Shifting bits right by k positions removes the k rightmost bits, which for a positive integer has the same effect as dividing by 2^k and discarding any remainder — for example, shifting 6 right by 1 gives 3.

Example: Right Shift

#include <iostream>
using namespace std;
int main() {
	int n = 6;
	cout << n << " >> 1 = " << (n >> 1) << " (same as dividing by 2, remainder discarded)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 6;
		System.out.println(n + " >> 1 = " + (n >> 1) + " (same as dividing by 2, remainder discarded)");
	}
}

n = 6
print(f"{n} >> 1 = {n >> 1} (same as dividing by 2, remainder discarded)")

#include <stdio.h>
int main() {
	int n = 6;
	printf("%d >> 1 = %d (same as dividing by 2, remainder discarded)", n, n >> 1);
	return 0;
}

Bit Practice

These bit operations run directly on a CPU's native hardware instructions, making them extremely fast, which is why they show up as building blocks in flags, masks, hashing, and low-level performance-sensitive code.

Example: Bit Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Bit ops run on native CPU instructions -- extremely fast, used in flags, masks, hashing";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Bit ops run on native CPU instructions -- extremely fast, used in flags, masks, hashing");
	}
}

print("Bit ops run on native CPU instructions -- extremely fast, used in flags, masks, hashing")

#include <stdio.h>
int main() {
	printf("Bit ops run on native CPU instructions -- extremely fast, used in flags, masks, hashing");
	return 0;
}

🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Monotonic Queue Next Lesson → Common Bit Tricks