AND, OR, XOR, and NOT

What is a bit?

A bit is a binary digit: either 0 or 1. Binary represents numbers using powers of two rather than powers of ten. Bit manipulation reads or changes these individual digits using operations such as AND, OR, XOR, and shifts. A mask is a bit pattern used to select particular positions.

Example: Binary 101 means 1×4 + 0×2 + 1×1 = 5. The rightmost position represents 1, the next represents 2, and the next represents 4.

Helpful before this chapter

If these ideas are new, begin with:

Programming foundations

Understand the idea

AND keeps bits set in both; OR keeps either; XOR keeps differing bits; NOT flips the representation's bits. Python ~x equals -x-1, so mask to an explicit width for an unsigned complement.

Work through an example

With 0101 and 0011: AND=0001, OR=0111, XOR=0110. Four-bit NOT of 0101 is 1010; Python ~5 alone is -6.

Time and space complexity

O(1) fixed-word operations; O(bit length) scale for large integers.

Why it works

Each result bit follows the operator truth table independently.

Common mistakes

Unmasked Python NOT is not a nonnegative fixed-width complement.
XOR cancels equal pairs but not arbitrary repeats.

Chapter lab · Python implementation

Bit operations treat an integer as binary positions. Our lab clears the lowest set bit repeatedly and enumerates subsets with masks. Examples use nonnegative integers unless an explicit width is supplied. Python integers are unbounded, so signed NOT and shifting differ from unsigned fixed-width machine examples.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def count_bits(value):
    if value<0: raise ValueError('nonnegative value required')
    count=0
    while value:
        value &= value-1
        count+=1
    return count

def subsets_mask(values):
    output=[]
    for mask in range(1<<len(values)):
        output.append([x for i,x in enumerate(values) if mask & (1<<i)])
    return output

def complement(value,width):
    if width<1 or not 0<=value<(1<<width):
        raise ValueError('value must fit width')
    return (~value)&((1<<width)-1)

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert count_bits(13)==3 and count_bits(0)==0
assert complement(5,4)==10
assert subsets_mask(['a','b'])==[[],['a'],['b'],['a','b']]
assert all(count_bits(x)==bin(x).count('1') for x in range(256))

CHECK YOUR UNDERSTANDING