1.2 - Bitwise Logic in x86 (Intel Syntax)

Bitwise Logic in X86

Recap

• Bitwise operations compare each bit pair individually:
  • and a, b → 1 only if both bits are 1.
  • or a, b → 1 if either bit is 1.
  • xor a, b → 1 if bits differ.
  • not a → flips all bits.

Example:

rax = 10101010
rbx = 00110011
and rax, rbx = 00100010

Here are some truth tables for reference:

• AND

  A | B | X
  ---+---+---
  0 | 0 | 0
  0 | 1 | 0
  1 | 0 | 0
  1 | 1 | 1

• OR

  A | B | X
  ---+---+---
  0 | 0 | 0
  0 | 1 | 1
  1 | 0 | 1
  1 | 1 | 1

• XOR

  A | B | X
  ---+---+---
  0 | 0 | 0
  0 | 1 | 1
  1 | 0 | 1
  1 | 1 | 0

---

Challenge Requirement

• Goal: compute (rdi AND rsi) and place result in rax.
• Restriction: cannot use mov or xchg.
• Allowed: arithmetic/logical instructions like and, or, xor.

---

Strategy

1. and works in place: and dest, src → dest = dest & src.
2. We want rax = rdi & rsi.
3. Without mov, we must transport the value of rdi into rax another way.

Trick: XOR-swap / zero+add

• xor rax, rax → zeroes rax (legal).
• add rax, rdi → now rax = rdi.
• Then: and rax, rsi.

---

Final Assembly

.intel_syntax noprefix
.global _start
.section .text
_start:
    xor rax, rax        ; clear rax without using mov
    add rax, rdi        ; rax = rdi
    and rax, rsi        ; rax = rdi & rsi
    ; result now stored in rax

---

Explanation

• Step 1: xor rax, rax zeroes rax.
• Step 2: add rax, rdi → since rax=0, result = rdi.
• Step 3: and rax, rsi → computes the desired rdi & rsi.

Thus, rax contains the final result using only logic and arithmetic, not mov or xchg.

Bitwise Logic: Checking Even/Odd with Only and, or, xor

Concept

• Even/Odd numbers in binary:
  • Even numbers always have the least significant bit (LSB) = 0.
  • Odd numbers always have LSB = 1.
• Therefore:

  if (rdi & 1) == 0 → even
  if (rdi & 1) == 1 → odd
  

• We want:
  • rax = 1 if even.
  • rax = 0 if odd.

---

Strategy (No mov, only and, or, xor)

1. Extract LSB of rdi: and rax, rdi, 1 (but we don’t have mov, so we need a trick).

2. Use XOR inversion:

   • If LSB=0 (even), we want output = 1.
   • If LSB=1 (odd), we want output = 0.

This is exactly the NOT of the LSB.
But since we don’t have not, we can simulate it with xor …, 1.

---

Implementation

.intel_syntax noprefix
.global _start
.section .text
_start:
    xor rax, rax        ; rax = 0
    or  rax, rdi        ; rax = rdi
    and rax, 1          ; rax = rdi & 1  (extract LSB)
    xor rax, 1          ; invert bit: if 0→1 (even), if 1→0 (odd)
    ; rax now contains y

---

Walkthrough Example

• If rdi = 4 (binary 100):
  • rax = rdi & 1 = 0
  • rax ^ 1 = 1 ✅ (even → 1).
• If rdi = 5 (binary 101):
  • rax = rdi & 1 = 1
  • rax ^ 1 = 0 ✅ (odd → 0).

---

Result: rax correctly holds 1 if rdi is even, else 0, using only and, or, xor.

Resources

---

Resource	Description
	Next note