Algorithms
  • Master AND, OR, XOR, NOT, and shift operations with clear examples
  • Understand how to set, clear, toggle, and check specific bits
  • Learn common bit manipulation patterns like checking power of 2
  • Recognize operator precedence and common pitfalls in bit operations

Basic Bit Operations

Now that you understand what bits are, let's get our hands dirty with the actual operations. There are six fundamental bit operations, and once you internalize them, a whole category of programming tricks becomes available.

The key to understanding these operations is thinking visually. Imagine two binary numbers lined up, bit by bit, and applying a rule to each pair. That's all bit operations are.

AND (&) - The Filter

Think of AND as a filter that only lets through bits that are set in both numbers.

Here's the rule: a bit in the result is 1 only if both input bits are 1. If either is 0, the result is 0.

  1010  (10 in decimal)
& 1100  (12 in decimal)
------
  1000  (8 in decimal)

Let's trace through this bit by bit:

  • Position 3: 1 AND 1 = 1
  • Position 2: 0 AND 1 = 0
  • Position 1: 1 AND 0 = 0
  • Position 0: 0 AND 0 = 0

Result: 1000

The AND operation is like asking "which bits are set in BOTH numbers?" Only the bits that are 1 in both numbers survive.

When you'd use this: Checking if specific bits are set.

Say you have a number representing permissions, and you want to know if the "read" bit (position 2) is set:

permissions = 13  # binary: 1101
READ = 4          # binary: 0100 (only bit 2 is set)

if permissions & READ:
    print("Has read permission")

The AND operation masks out everything except the read bit. If the result is non-zero, that bit was set.

Another common use: checking if a number is even.

if number & 1 == 0:
    print("Even")

Why does this work? Because the last bit is 0 for even numbers and 1 for odd numbers. ANDing with 1 isolates that bit.

OR (|) - The Combiner

OR is the opposite of AND. It sets a bit to 1 if either input bit is 1.

  1010  (10)
| 1100  (12)
------
  1110  (14)

Bit by bit:

  • Position 3: 1 OR 1 = 1
  • Position 2: 0 OR 1 = 1
  • Position 1: 1 OR 0 = 1
  • Position 0: 0 OR 0 = 0

OR is like asking "which bits are set in EITHER number?" Any bit that's 1 in either input becomes 1 in the output.

When you'd use this: Setting bits or combining flags.

If you want to grant both read and write permissions:

READ = 4      # binary: 0100
WRITE = 2     # binary: 0010

permissions = READ | WRITE  # binary: 0110 (both bits set)

You're combining the two permission flags into one value that has both bits set.

Or if you want to ensure a specific bit is set:

number = 5        # binary: 0101
number |= 8       # binary: 1000
# Result: 13      # binary: 1101

The OR ensures bit 3 is set, regardless of whether it was already set.

XOR (^) - The Difference Finder

XOR (exclusive or) is the weird one. It sets a bit to 1 only if the bits are different.

  1010  (10)
^ 1100  (12)
------
  0110  (6)

Bit by bit:

  • Position 3: 1 XOR 1 = 0 (same, so 0)
  • Position 2: 0 XOR 1 = 1 (different, so 1)
  • Position 1: 1 XOR 0 = 1 (different, so 1)
  • Position 0: 0 XOR 0 = 0 (same, so 0)

XOR asks "which bits are different?" It lights up the bits that differ between the two numbers.

When you'd use this: XOR has some sneaky properties that make it incredibly useful.

Property 1: XORing a number with itself gives 0.

5 ^ 5 = 0

Property 2: XORing with 0 gives the original number.

5 ^ 0 = 5

Property 3: XOR is its own inverse.

a ^ b ^ b = a

These properties enable some clever tricks:

Toggling bits: Want to flip a specific bit?

number ^= (1 << position)  # Toggle the bit at 'position'

Finding the unique element: If you have an array where every element appears twice except one, you can find the unique one by XORing all elements together. The duplicates cancel out (a ^ a = 0), leaving only the unique element.

def find_unique(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

# [4, 2, 4, 5, 2] → returns 5

Swapping without a temporary: This is more of a party trick than practical code, but it demonstrates XOR's properties:

a = 5
b = 7

a ^= b  # a = 5 ^ 7
b ^= a  # b = 7 ^ (5 ^ 7) = 5
a ^= b  # a = (5 ^ 7) ^ 5 = 7

# a and b are now swapped

This works because XOR undoes itself. But honestly, just use a temporary variable in real code—it's clearer.

NOT (~) - The Inverter

NOT flips every bit. 0 becomes 1, 1 becomes 0.

~1010 = 0101

Simple, right? Except there's a catch: how negative numbers work.

Most systems use "two's complement" for negative numbers. In this system, flipping all bits of a number n gives you -(n+1).

~5 = -6
~0 = -1
~(-1) = 0

This seems weird until you understand two's complement, but for now, just remember: ~n = -(n+1).

When you'd use this: Usually in combination with other operations.

To clear a specific bit, you need to AND with a mask that has all bits set except the one you want to clear:

# Clear bit 2
number &= ~(1 << 2)

Breaking this down:

  • 1 << 2 creates 0100 (only bit 2 set)
  • ~(1 << 2) creates 1011 (all bits set except bit 2)
  • ANDing with this mask clears bit 2 while leaving others unchanged

Left Shift (<<) - Multiply by Powers of 2

Left shift moves all bits to the left and fills in zeros on the right.

  1010  (10)
<< 1
------
 10100  (20)

Each left shift multiplies the number by 2. Shift by 2, multiply by 4. Shift by 3, multiply by 8.

5 << 1  # 10
5 << 2  # 20
5 << 3  # 40

Why is this useful? Because shifting is faster than multiplication. If you need to multiply by a power of 2, shifting is the way to go.

Common use: Creating bit masks.

mask = 1 << n  # Creates a number with only bit n set

If n=3, you get 1000 (8 in decimal). This is how you create masks for setting, clearing, or checking specific bits.

Right Shift (>>) - Divide by Powers of 2

Right shift moves all bits to the right, discarding bits that fall off the end.

 10100  (20)
>> 1
------
  1010  (10)

Each right shift divides by 2 (integer division).

20 >> 1  # 10
20 >> 2  # 5
20 >> 3  # 2

Again, this is faster than division when you're dividing by a power of 2.

The catch: What happens to negative numbers?

There are two types of right shift:

  • Logical shift: Fill with zeros (treats the number as unsigned)
  • Arithmetic shift: Fill with copies of the sign bit (preserves the sign)

Most languages use arithmetic shift for signed integers, which means negative numbers stay negative:

-8 >> 1  # -4 (not 2147483644)

If you need logical shift in a language that does arithmetic shift, you usually need to cast to unsigned first or use a different operator (like >>> in Java).

Putting It All Together

Here's a practical example: suppose you're building a simple permissions system with four permissions.

# Define permissions as powers of 2
READ = 1 << 0      # 0001
WRITE = 1 << 1     # 0010
EXECUTE = 1 << 2   # 0100
DELETE = 1 << 3    # 1000

# Grant read and execute
user_perms = READ | EXECUTE  # 0101

# Check if user has write
has_write = (user_perms & WRITE) != 0  # False

# Grant write
user_perms |= WRITE  # 0111

# Revoke execute
user_perms &= ~EXECUTE  # 0011

# Toggle delete
user_perms ^= DELETE  # 1011

# Check what permissions user has
if user_perms & READ:
    print("Can read")
if user_perms & WRITE:
    print("Can write")
if user_perms & EXECUTE:
    print("Can execute")
if user_perms & DELETE:
    print("Can delete")

In a single integer, you're storing and manipulating four separate boolean flags. This is far more efficient than using four separate variables or an array.

Common Patterns Worth Memorizing

Check if power of 2:

def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

Powers of 2 have exactly one bit set: 1000, 0100, 0010, 0001. Subtracting 1 flips all bits up to and including the set bit: 0111, 0011, 0001, 0000. ANDing them gives 0.

Count set bits (naive approach):

def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

Check each bit with n & 1, then shift right to check the next.

Isolate rightmost set bit:

rightmost = n & (-n)

This works because of how two's complement negation works. If n = 1010, then -n = 0110, and n & -n = 0010.

Clear rightmost set bit:

n &= (n - 1)

If n = 1010, then n - 1 = 1001, and n & (n-1) = 1000.

When Bit Operations Go Wrong

Mistake 1: Operator precedence

# Wrong
if flags & MASK == 0:  # == has higher precedence than &

# Right
if (flags & MASK) == 0:

Bitwise operators have lower precedence than you might expect. When in doubt, use parentheses.

Mistake 2: Assuming 32-bit integers

# Might not work on 64-bit systems
mask = ~0 >> 1  # Expected: 0x7FFFFFFF, might get 0x7FFFFFFFFFFFFFFF

If you need specific bit widths, mask explicitly or use fixed-width types.

Mistake 3: Right shifting negative numbers

# Behavior varies by language
-8 >> 1  # Might be -4 or a huge positive number

Know your language's right shift semantics.

The Bigger Picture

These six operations—AND, OR, XOR, NOT, left shift, right shift—are your tools. Individually, they're simple. But combined cleverly, they can solve problems that would otherwise require loops, conditionals, or complex logic.

The skill is recognizing when a problem can be solved with bits. Permissions systems, state machines, subset generation, finding duplicates, cryptographic operations—all of these often have elegant bit-based solutions.

Don't try to memorize every trick. Understand the fundamental operations deeply, and the tricks will make sense when you encounter them.