RavnaryA Knowledge Platform
Colour theme

Card 01/ 08

Take the quiz

ConceptDifficulty: Intermediate3 min

Bit Manipulation: Reading an Integer as a Row of Switches

Every integer is a row of bits, and six operators read, combine and move those bits in one step each.

Bit manipulation solves a problem by reading and changing the single bits of an integer, each in one step. The cue is a property of the problem: the question is about a small set of on-or-off choices, about values that cancel in pairs, or about powers of two. A bit is one binary digit, 0 or 1, and an integer is a row of them: in 1010, read from the right, the bits are worth 1, 2, 4 and 8, and the ones that are on add up to 10.

Six operators work on every bit position at once. AND (&) keeps a bit where both inputs have it, OR (|) where either has it, and XOR (^, exclusive or) where exactly one has it. NOT (~) flips every bit. A left shift (<<) moves every bit one place towards the high end, doubling the value, and a right shift (>>) moves every bit towards the low end, dropping the last one and halving the value. The table applies each to a = 10 and b = 6.

The six operators on a = 10 and b = 6, from a run
OperatorSymbolabResult in bitsResult
AND&1010011000102
OR|10100110111014
XOR^10100110110012
NOT~1010not used11110101, the lowest eight bits−11
Left shift by 1<<1010not used1010020
Right shift by 1 1010not used1015

The trace shows the same values as rows of eight bits, the most significant first, so each result can be read column by column against a and b.

a = 10, b = 6 and each result, as eight bits

Inputa = 10, b = 6

  1. a = 10

    1. 0
    2. 0
    3. 0
    4. 0
    5. 1
    6. 0
    7. 1
    8. 0

    a = 10: the bits worth 8 and 2 are on

  2. b = 6

    1. 0
    2. 0
    3. 0
    4. 0
    5. 0
    6. 1
    7. 1
    8. 0

    b = 6: the bits worth 4 and 2 are on

  3. a AND b = 2

    1. 0
    2. 0
    3. 0
    4. 0
    5. 0
    6. 0
    7. 1
    8. 0

    AND keeps only the bit worth 2, the one both share

  4. a OR b = 14

    1. 0
    2. 0
    3. 0
    4. 0
    5. 1
    6. 1
    7. 1
    8. 0

    OR keeps every bit either has: 8, 4 and 2

  5. a XOR b = 12

    1. 0
    2. 0
    3. 0
    4. 0
    5. 1
    6. 1
    7. 0
    8. 0

    XOR keeps the bits exactly one has, 8 and 4, and the shared 2 cancels

  6. NOT a = −11

    1. 1
    2. 1
    3. 1
    4. 1
    5. 0
    6. 1
    7. 0
    8. 1

    NOT flips every bit; these are the lowest eight bits of −11

  7. a << 1 = 20

    1. 0
    2. 0
    3. 0
    4. 1
    5. 0
    6. 1
    7. 0
    8. 0

    A left shift moves every bit up one place and doubles the value

  8. a >> 1 = 5

    1. 0
    2. 0
    3. 0
    4. 0
    5. 0
    6. 1
    7. 0
    8. 1

    A right shift moves every bit down one place, drops the lowest, and halves the value

ResultAND 2, OR 14, XOR 12, NOT −11, left shift 20, right shift 5.

NOT a is −11, not 5, because of how negative numbers are stored. Java's int and TypeScript's bitwise operators work on 32 bits in two's complement, an encoding in which the leftmost bit counts as −2³¹ instead of +2³¹, so a number with that bit on is negative and ~x is always −x − 1. Python's integers have no fixed width: a negative number behaves as if it had infinitely many 1 bits on the left, and ~10 is −11 there too. The three languages agree on small non-negative values and part company at the 32nd bit.

A wall panel of light switches works the same way: each switch has a value set by its position, and the number written on the panel is the sum of the switches that are on. The likeness breaks at the edge of the panel. A real panel has a fixed number of switches, while a Python integer grows as many as it needs, and in Java and TypeScript the leftmost switch also decides the sign.

← → move through sections and cards