Bitwise Operations

Bitwise operations let you work with the individual bits of an integer. They’re super powerful for bit manipulation, optimization tricks, and things like generating all subsets of a set.

Binary Numbers

Computers store integers in binary — using only 0 and 1. We call a bit to be set if it is equal to 1. Each position (bit) represents a power of 2:

Bit position:  7  6  5  4  3  2  1  0
Value:       128 64 32 16  8  4  2  1

To get the value of a binary number, you add the powers of 2 where there is a 1.

Examples

00000110  =  4 + 2       = 6
00001010  =  8 + 2       = 10
00001100  =  8 + 4       = 12
00000001  =  1           = 1
00000000  =  0           = 0

So when we do bitwise operations (&, |, ^, etc.), we are combining or modifying these individual bits.

Two’s Complement and Negative Numbers

So far we only talked about non-negative integers. But in C++ (and basically all modern CPUs), signed integers are stored in a format called two’s complement.

Idea:

• Use the highest bit (most significant bit) as a sign bit.

Let’s pretend we have 8-bit signed integers.

Bit position:  7  6  5  4   3  2  1  0
Value:       -128 64 32 16  8  4  2  1

The range of an 8-bit signed number is:

-128 ... +127

How positive numbers look

Positive numbers (and zero) look the same as before:

00000101 = 5
00000000 = 0
00001010 = 10

How negative numbers are stored (two’s complement)

To get -x in two’s complement:

1. Write x in binary.
2. Flip all bits (0 -> 1, 1 -> 0).
3. Add 1.

Example: -5 on 8 bits.

+5        = 00000101
flip      = 11111010
+ 1       = 11111011  = -5

Check -1:

+1        = 00000001
flip      = 11111110
+ 1       = 11111111  = -1

So:

11111111 = -1
11111011 = -5
10000000 = -128

Why this is nice

With two’s complement:

• Normal binary addition still works for negative numbers.
• There is only one representation of zero.
• Subtraction is just a + (-b).

Right shift and negatives

For unsigned types, >> always shifts in 0 bits on the left.

For signed types, most compilers perform an arithmetic right shift:

• They copy the sign bit (the top bit), so negative numbers stay negative as you shift.

Example (assuming arithmetic shift):

x  = -4   -> 11111100 (8-bit view)
x >> 1    -> 11111110 (still negative: -2)

This is why, when you care about raw bits, it’s often safer to use unsigned types (uint32_t, unsigned long long, etc.).

The Main Bitwise Operators

All of these work on integer types (int, long long, etc.):

Operator	Name	What it does (bitwise)
&	AND	1 if both bits are 1, otherwise 0
|	OR	1 if at least one bit is 1, otherwise 0
^	XOR	1 if bits are different, otherwise 0
~	NOT / complement	Flips all bits (1 → 0, 0 → 1)
<<	Left shift	Shifts bits left (multiply by powers of 2)
>>	Right shift	Shifts bits right (divide by powers of 2)

Seeing Bitwise Operations in Binary

Let’s use small numbers and pretend they’re 8-bit for clarity:

a = 6   -> 00000110
b = 10  -> 00001010

AND &

a & b   -> 00000110
           00001010
           --------
           00000010  = 2

OR |

a | b   -> 00000110
           00001010
           --------
           00001110  = 14

XOR ^

a ^ b   -> 00000110
           00001010
           --------
           00001100  = 12   (bits that are different become 1)

NOT ~

~a      -> 11111001   (on 8 bits, but in real C++ it’s on full `int`/`long long`)

Shifts

a << 1  -> 00001100  = 12   (6 * 2)
a << 2  -> 00011000  = 24   (6 * 4)

b >> 1  -> 00000101  = 5    (10 / 2)
b >> 2  -> 00000010  = 2    (10 / 4, integer division)

Simple C++ Example

#include <iostream>
using namespace std;

void printBits(int x) {
    for (int i = 7; i >= 0; i--) {
        cout << ((x >> i) & 1);
    }
}

int main() {
    int a = 6;   // 00000110
    int b = 10;  // 00001010

    cout << "a = "; printBits(a); cout << " (" << a << ")\n";
    cout << "b = "; printBits(b); cout << " (" << b << ")\n\n";

    cout << "a & b = "; printBits(a & b); cout << " (" << (a & b) << ")\n";
    cout << "a | b = "; printBits(a | b); cout << " (" << (a | b) << ")\n";
    cout << "a ^ b = "; printBits(a ^ b); cout << " (" << (a ^ b) << ")\n";
    cout << "~a    = "; printBits((unsigned char)~a); cout << " (only low 8 bits)\n";

    cout << "a << 1 = "; printBits(a << 1); cout << " (" << (a << 1) << ")\n";
    cout << "b >> 1 = "; printBits(b >> 1); cout << " (" << (b >> 1) << ")\n";
}

The function printBits goes through all bit positions i (from 7 to 0), and does x >> i, which shifts the given value x that many positions to the right. This makes the i-th bit come to the rightmost position. Then it does & 1 which “ANDs” that value with 00000001, which has an effect of keeping only the rightmost bit of that value. So these two operations together result in extracting the bit at the i-th position.