Bitwise Operators

Part I · Module 4 · Chapter 4.6 · Bitwise Operators

1. Seeing the Bits

Everything here is easier with a way to print a number in binary. Tcl's format can do this from 8.6 onwards, but a small helper works on every version and is itself a use of two of the operators:

proc bits {n width} {
    set out ""
    for {set i [expr {$width - 1}]} {$i >= 0} {incr i -1} {
        append out [expr {($n >> $i) & 1}]
    }
    return $out
}

puts [bits 10 8]
puts [bits 255 8]

00001010
11111111

It shifts each bit down to position 0 and masks off everything else. You can read it properly after Module 9; for now, use it.

You can also write binary literals directly with 0b, and hexadecimal with 0x:

puts "0b1010 = [expr {0b1010}]"
puts "0xFF   = [expr {0xFF}]"

0b1010 = 10
0xFF   = 255

2. The Six Operators

proc bits {n width} {
    set out ""
    for {set i [expr {$width - 1}]} {$i >= 0} {incr i -1} {
        append out [expr {($n >> $i) & 1}]
    }
    return $out
}

puts "1100 & 1010 = [bits [expr {0b1100 & 0b1010}] 4]   (and)"
puts "1100 | 1010 = [bits [expr {0b1100 | 0b1010}] 4]   (or)"
puts "1100 ^ 1010 = [bits [expr {0b1100 ^ 0b1010}] 4]   (exclusive or)"
puts "1 << 4      = [expr {1 << 4}]"
puts "256 >> 4    = [expr {256 >> 4}]"
puts "~0          = [expr {~0}]"

1100 & 1010 = 1000   (and)
1100 | 1010 = 1110   (or)
1100 ^ 1010 = 0110   (exclusive or)
1 << 4      = 16
256 >> 4    = 16
~0          = -1

• & keeps a bit only where both have it.
• | keeps a bit where either has it.
• ^ keeps a bit where exactly one has it.
• << moves bits left, which multiplies by two each time.
• >> moves bits right, which halves.
• ~ flips every bit.

3. Why ~0 Is -1

The last result is worth explaining rather than skipping.

puts "~0 = [expr {~0}]"
puts "~5 = [expr {~5}]"
puts "~-1 = [expr {~-1}]"

~0 = -1
~5 = -6
~-1 = 0

Tcl's integers are signed, so flipping every bit of 0 gives a value whose bits are all ones, and that represents -1. The pattern is ~n == -n - 1.

This matters because ~ is rarely what you want on its own. Its normal use is clearing a bit, where it appears as & ~$MASK — §4.

4. The Flags Idiom

This is the practical use. Several independent yes/no settings live in one number, one per bit:

proc bits {n width} {
    set out ""
    for {set i [expr {$width - 1}]} {$i >= 0} {incr i -1} {
        append out [expr {($n >> $i) & 1}]
    }
    return $out
}

set READ  0b001
set WRITE 0b010
set EXEC  0b100

set perms [expr {$READ | $WRITE}]
puts "start            = [bits $perms 3]"

puts "has READ?        [expr {($perms & $READ) != 0}]"
puts "has EXEC?        [expr {($perms & $EXEC) != 0}]"

set perms [expr {$perms | $EXEC}]
puts "after add EXEC   = [bits $perms 3]"

set perms [expr {$perms & ~$WRITE}]
puts "after drop WRITE = [bits $perms 3]"

start            = 011
has READ?        1
has EXEC?        0
after add EXEC   = 111
after drop WRITE = 101

Four operations, and they are the whole idiom:

The value of this over three separate variables is that it travels as one number — easy to store, pass, or compare in one go.

5. The Precedence Trap

Look again at the test row above. The parentheses around $f & $FLAG are not decoration.

Here is the broken form and the correct form, run against all three flags of a value that has READ and EXEC but not WRITE:

set perms 0b101          ;# READ and EXEC set, WRITE clear

foreach {name flag} {READ 0b001  WRITE 0b010  EXEC 0b100} {
    puts [format "%-6s  no parentheses: %s    with parentheses: %s" $name \
        [expr {$perms & $flag == $flag}] \
        [expr {($perms & $flag) != 0}]]
}

READ    no parentheses: 1    with parentheses: 1
WRITE   no parentheses: 1    with parentheses: 0
EXEC    no parentheses: 1    with parentheses: 1

The unparenthesised form answered 1 for all three — including WRITE, which is not set.

It is not testing flags at all. == binds tighter than & — Chapter 4.2 §5 — so $perms & $flag == $flag is $perms & ($flag == $flag), and $flag == $flag is always 1. The expression reduces to $perms & 1, which is the low bit of perms.

So the broken test reports the value of one fixed bit, no matter which mask you pass it. It happens to be correct whenever that bit is the one you asked about, which is how it survives review.

6. Shifts, Precisely

puts "1 << 10   = [expr {1 << 10}]"
puts "1 << 64   = [expr {1 << 64}]"
puts "-8 >> 1   = [expr {-8 >> 1}]"
puts "7 >> 1    = [expr {7 >> 1}]"

1 << 10   = 1024
1 << 64   = 18446744073709551616
-8 >> 1   = -4
7 >> 1    = 3

Three things worth noting.

No overflow. 1 << 64 would wrap to 0 in a 64-bit C integer. Tcl's integers grow, so it gives the exact value — Chapter 3.5 §8.

Right shift keeps the sign. -8 >> 1 is -4, not a large positive number. The sign bit is preserved.

Right shift discards, it does not round. 7 >> 1 is 3, the same as 7 / 2.

A negative shift count is an error rather than a shift the other way:

puts [catch {expr {1 << -1}} m]
puts $m

1
negative shift argument

7. Whole Numbers Only

puts [catch {expr {1.5 & 1}} m]
puts $m

1
can't use floating-point value as operand of "&"

Every bitwise operator requires whole numbers. There is no rounding and no conversion.

One scope note: bit manipulation has a much larger role in hardware and protocol work — register fields, packed formats, byte order. None of that is Part I, and none of it needs anything beyond the six operators here.

8. Common Mistakes

Omitting the parentheses in a flag test. §5. The single most damaging one.

Using == $MASK for a multi-bit mask. Prefer != 0 unless you genuinely mean "all of these bits".

Expecting ~ to give a small positive number. §3. It gives -n - 1.

Expecting << to overflow or wrap. §6. Tcl's integers grow.

Using a bitwise operator on a real number. §7.

Confusing & with &&. & works on bits, && on truth values. 1 & 2 is 0; 1 && 2 is 1.

9. Exercises

Exercise 1 — the three combiners. Using the bits helper, print the result of 0b1011 & 0b0110, 0b1011 | 0b0110, and 0b1011 ^ 0b0110 in four-bit form. Predict each first.

Exercise 2 — build a flags value. Define VERBOSE, DRYRUN and FORCE as 1, 2 and 4. Turn on VERBOSE and FORCE, print the bits, test for each of the three, then turn FORCE off and print again.

Exercise 3 — see the trap. Reproduce §5 with your FORCE flag. Confirm the unparenthesised version gives the wrong answer, and say in one sentence what it actually computed.

Exercise 4 — complement. Predict ~1, ~7 and ~-5, then check. What is the rule?

Exercise 5 — shifts as arithmetic. Show that $n << 3 equals $n * 8 for three values of n, then find a value where $n >> 1 and $n / 2 differ. (Hint: try a negative odd number, and recall Chapter 3.10 §6.)

Exercise 6 — & versus &&. Predict expr {2 & 4} and expr {2 && 4}, then check. Explain why they differ.

10. Remember

• Six operators work on the bits of a whole number: & | ^ ~ << >>.
• Write literals as 0b1010 or 0xFF. A small bits helper prints them back on any version.
• ~n is -n - 1, because Tcl's integers are signed. Its normal use is & ~$MASK.
• The flags idiom is four operations: set with |, clear with & ~, test with (f & FLAG) != 0, toggle with ^.
• Always parenthesise the mask. $flags & $MASK == $MASK tests whether $flags is odd.
• Shifts do not overflow, right shift preserves the sign, and a negative shift count is an error.
• Whole numbers only. Real numbers are rejected.
• & is not &&. Bits versus truth values.

Next: choosing between two values inside an expression.