Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 40 ยท Core Instructions

Logic, Shifts and Bit Tricks

Learn the x86-64 bitwise instructions and, or, xor, not, test, shl, shr, sar and rotates, plus masks, xor zeroing, popcount and power-of-two bit tricks.

Arithmetic treats a register as a number. Logic instructions treat it as a row of independent bits, which is exactly what you need for flags, hardware registers, packed fields, network headers, hashes and compression. Shifts slide the whole row left or right, which turns out to be multiplication and division by powers of two as well.

These instructions are small, fast (usually one cycle) and everywhere in compiled code. After this lesson you will recognise xor eax, eax, test edi, edi, shl rax, 3 and and eax, 0xFF on sight, understand which flags they leave behind, and be able to use the classic bit tricks (clear the lowest set bit, test for a power of two, count bits) in your own routines.

and, or, xor, not

Each operates on all bits in parallel, with the same truth tables as &, |, ^ and ~ in C:

a b and or xor
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

not x flips every bit (one's complement). Unlike the others it does not change any flags. The two-operand forms and, or and xor always set CF = 0 and OF = 0, and set ZF, SF and PF from the result. That makes them good for testing the value: after and eax, eax, ZF tells you whether eax is zero.

test: and without the result

test a, b computes a and b, sets the flags, and throws the result away. Its main use is checking bits and testing for zero:

NASM
test eax, eax        ; ZF=1 if eax is 0, SF=1 if eax is negative
jz   is_zero
test edi, 1          ; is bit 0 set? (odd number)
jnz  is_odd

test eax, eax is shorter than cmp eax, 0, so compilers prefer it. It is the machine form of C's if (x).

The xor zeroing idiom

xor eax, eax sets eax to zero because every bit xored with itself is 0. It is 2 bytes instead of the 5 needed for mov eax, 0, the CPU recognises it as "result is zero, no dependency on the old value", and thanks to the 32-bit zero-extension rule (see the x86-64 register set) it clears all 64 bits of rax. The price: it modifies flags, where mov does not. Occasionally you will see mov eax, 0 between a cmp and a jcc precisely for that reason.

Masks

A mask is a constant with 1s in the positions you care about. With one instruction each:

Goal Instruction C
Keep only some bits and eax, 0x0F x & 0x0F
Set bits or eax, 0x80 x |= 0x80
Clear bits and eax, ~0x80 (the assembler computes 0xFFFFFF7F) x &= ~0x80
Toggle bits xor eax, 0x01 x ^= 1
Test bits test eax, 0x04 if (x & 4)

The x86 bt (bit test) family (bt, bts, btr, btc) tests, sets, clears or complements one bit by index and puts the old bit in CF. The toy program below applies a mask to a byte and prints the bits so you can see each operation.

JS and, or, xor, not and test on a byte

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The parity flag PF is 1 when the low byte of the result has an even number of 1 bits; it is a leftover from serial-communication days and almost never used in modern code.

Shifts: shl, shr, sar

A shift moves every bit n places. The bit shifted out lands in CF; the new bits on the other end are filled according to the instruction.

  • shl x, n (shift left, same as sal): zeros enter from the right. Equals x * 2^n.
  • shr x, n (logical shift right): zeros enter from the left. Equals unsigned x / 2^n.
  • sar x, n (arithmetic shift right): copies of the sign bit enter from the left, so negative numbers stay negative. Equals signed x / 2^n, rounded toward negative infinity.

The count is an immediate or the register cl. The hardware masks the count to 5 bits (32-bit operands) or 6 bits (64-bit): shifting a 32-bit value by 33 is the same as shifting by 1. A count of zero changes nothing, including the flags. In C, shifting by an amount >= the width is undefined behaviour precisely because machines disagree on what happens.

NASM
shl rax, 3       ; rax * 8
shr rax, 1       ; unsigned rax / 2
sar eax, 31      ; every bit becomes the sign bit: 0 or -1 (a handy mask)

Why sar rounds differently from C division

C truncates toward zero: -7 / 2 is -3. But sar on -7 gives -4 (floor). Compilers therefore emit extra instructions, adding (2^n - 1) to negative numbers before shifting, whenever you write x / 2 on a signed integer. For unsigned numbers shr alone is exact.

Rotates

rol and ror rotate: bits shifted out re-enter at the other end, and the last bit moved also lands in CF. rcl and rcr rotate through the carry flag as if it were a 9th (or 33rd, 65th) bit; they are the building blocks of multi-word shifts. Rotates appear in hash functions and ciphers, where no information may be lost.

flowchart LR
  subgraph shl
    direction LR
    C1["CF"] --- B1["b7 b6 ... b0"] --- Z1["0"]
  end
  subgraph rol
    direction LR
    B2["b7 b6 ... b0"] -->|"b7 re-enters at b0"| B3["b7 b6 ... b0 (rotated)"] --- C2["CF = copy of the bit that wrapped"]
  end

Shifts discard the bit that falls off (into CF); rotates feed it back in.

The next demo implements the shifts and rotates on 8 bits and prints the result and CF, including the signed vs unsigned difference.

JS Shifts and rotates on 8 bits

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Compare the two right shifts of 10110010 (178 unsigned, -78 signed). shr by 2 gives 44 (unsigned divide: 178 / 4 = 44.5, floored), while sar by 2 gives -20 (signed: -78 / 4 = -19.5, floored to -20). And sar of -7 by 1 gives -4, the floor of -3.5.

Bit tricks you will meet everywhere

A handful of identities show up in compiler output and in hand-optimised code. All follow from how two's complement subtraction affects the low bits.

  • Clear the lowest set bit: x & (x - 1). Subtracting 1 flips the lowest 1 and all the zeros below it, so the and clears exactly that bit.
  • Test for a power of two: x != 0 && (x & (x - 1)) == 0, because a power of two has exactly one bit set.
  • Isolate the lowest set bit: x & -x (since -x is ~x + 1). The instructions blsi and blsr (BMI1) do these two directly.
  • Count the 1 bits (popcount): repeat x &= x - 1 until x is zero, counting the loops. CPUs with the popcnt instruction do it in one go.
  • Multiply/divide by powers of two: shl/shr. x % 8 for unsigned x is x & 7, and x / 8 is x >> 3.
  • Swap without a temporary: a ^= b; b ^= a; a ^= b (a curiosity; xchg is better in real code).
JS Bit tricks in 32 bits

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Real CPUs also offer dedicated instructions for several of these (popcnt, lzcnt, tzcnt, bsf, bsr), and compilers turn a loop like the one above into a single popcnt when the target supports it. Knowing the underlying identities lets you read what the compiler produced and write the loop yourself when it does not.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does xor eax, eax do, and why do compilers prefer it to mov eax, 0?

    A value xored with itself is 0 and the 32-bit write zero-extends into rax. The encoding is shorter than mov eax, 0 and the CPU treats it as a dependency-breaking zeroing idiom. The cost is that flags are modified.
  2. 2. What is the difference between shr and sar?

    shr is the logical (unsigned) right shift; sar is the arithmetic (signed) right shift that preserves the sign.
  3. 3. After test edi, edi which condition means edi was zero?

    test ands edi with itself and sets ZF when the result is zero, i.e. when edi is zero. It does not store the result.
  4. 4. What does x & (x - 1) compute?

    Subtracting 1 flips the lowest 1 bit and the zeros below it, so and-ing with x clears that lowest 1. Repeating until zero counts the set bits.
  5. 5. What is sar of the signed 8-bit value -7 (0b11111001) by 1?

    sar rounds toward negative infinity, so -7 / 2 gives -4 (0b11111100). C's division truncates toward zero and gives -3, so compilers add a correction for signed division.

Summary

  • and, or, xor work on all bits at once and set CF=OF=0 plus ZF, SF and PF; not changes no flags.
  • test a, b is and without storing the result; test eax, eax is the standard zero/sign check.
  • xor reg, reg zeroes a register compactly (and costs flags); masks set, clear, toggle and test chosen bits.
  • shl multiplies by powers of two; shr divides unsigned; sar divides signed (rounding toward negative infinity); the last bit out goes into CF.
  • Rotates (rol, ror, rcl, rcr) keep every bit; shift counts are masked to the operand width.
  • x & (x - 1) clears the lowest set bit, giving power-of-two tests and popcount loops.

Next: Flags: ZF, SF, CF, OF and How They Are Set.