Chapter 13 Exercises: Bit Manipulation

Open Assembly Language Project

Chapter 13 Exercises: Bit Manipulation

Section A: Bitmask Operations

Exercise 1. Write a single NASM instruction (or pair where unavoidable) for each operation. Inputs are in RAX; write results back to RAX:

(a) Isolate the high byte of RAX (bits 63:56) (b) Clear bits 15:8 of RAX (c) Set bits 7, 6, 5 of RAX simultaneously (d) Toggle bit 31 of RAX (e) Extract bits 19:12 of RAX (8-bit field) and shift to bits 7:0

Exercise 2. Given uint32_t flags in EAX, write NASM code for each operation:

(a) Test if bit 3 is set. Jump to .bit_set if so. Do not modify EAX. (b) Test if bits 3 AND 7 are BOTH set. Jump to .both_set if so. (c) Set bit 7 and clear bit 3 atomically (in one pass through the flags value).

Exercise 3. Write a NASM function uint64_t extract_field(uint64_t value, int start, int len) that extracts len bits starting at bit start from value. The result should be zero-extended to 64 bits.

value in RDI, start in RSI (0-63), len in RDX (1-64, but start+len ≤ 64)
Return in RAX

Use only SHR and masking (no BMI instructions). Then write an alternative using bextr (BMI1).

Exercise 4. Write a NASM function uint64_t insert_field(uint64_t dst, uint64_t src, int start, int len) that inserts the low len bits of src into dst at bit position start.

dst in RDI, src in RSI, start in RDX (0-63), len in RCX
Return modified dst in RAX

Section B: Bit Scanning and Counting

Exercise 5. Write NASM code to compute floor(log2(x)) for x > 0 in RDI. Return result in RAX. Use BSR.

Exercise 6. Write NASM code using TZCNT to find the position of the least significant set bit of RDI. Handle the case where RDI == 0 (return -1 or 64 as your convention).

Exercise 7. Implement uint64_t round_up_power2(uint64_t x) in NASM: - If x is 0, return 0 - If x is already a power of 2, return x - Otherwise, return the next power of 2 above x

Use BSR to find the position, then shift.

Exercise 8. Write a NASM function int64_t popcount(uint64_t x) that counts set bits using: (a) The POPCNT instruction (if available — assume it is) (b) The software parallel counting algorithm from the chapter

Exercise 9. Using only BLSR (BMI1), write a loop that processes each set bit of a 64-bit bitmask in RDI, calling a function process_bit(int bit_position) for each set bit. The bit position should be found using TZCNT.

Section C: XOR Applications

Exercise 10. Prove that the XOR swap is correct by tracing it with values RAX = 5, RBX = 9:

xor rax, rbx
xor rbx, rax
xor rax, rbx

Show the value of each register after each step.

Exercise 11. Why does the XOR swap fail when applied to the same register? Show what happens:

xor rax, rax
xor rax, rax
xor rax, rax

Exercise 12. Implement a function void xor_decrypt(uint8_t *data, size_t len, uint8_t key) in NASM that decrypts data XOR-encrypted with a single-byte key. The function should process as many bytes as possible 8 at a time (using the replicated-key technique), then handle the tail.

Hint: replicate the byte key to all 8 bytes of a 64-bit register using imul rcx, 0x0101010101010101.

Exercise 13. Write a NASM function int parity(uint64_t x) that returns 1 if x has an odd number of set bits, 0 if even. The efficient approach uses POPCNT and checks the low bit.

Section D: Classic Bit Manipulation Problems

Exercise 14. Write NASM code for each classic bit manipulation problem:

(a) Test if x is a power of 2 (result in ZF; 0 → ZF=1 counts as power of 2 for the test only) (b) Clear the rightmost set bit of x (e.g., 0b10110 → 0b10100) (c) Set all bits below the rightmost 0 (e.g., 0b10100 → 0b10111) (d) Count the number of 1s in odd bit positions of x (bits 1, 3, 5, ...)

Exercise 15. Implement the "bit trick" for computing the absolute value of a 64-bit signed integer using only arithmetic (no branches, no CMOV):

mask = x >> 63           (arithmetic right shift: all-ones if negative, all-zeros if positive)
abs(x) = (x XOR mask) - mask

Write this as a NASM function int64_t abs_branchless(int64_t x).

Exercise 16. Given two 64-bit integers A and B in RDI and RSI, compute the Hamming distance (number of bit positions where they differ) in RAX. Use POPCNT.

Exercise 17. Write a NASM function that converts a byte (0-255) to its binary string representation (8 ASCII characters '0' or '1', followed by a null byte). The byte is in RDI, the output buffer (9 bytes minimum) is in RSI.

Use bit extraction and write '0' (0x30) or '1' (0x31) for each bit, MSB first.

Section E: Applied Bit Manipulation

Exercise 18. A network packet's IPv4 Type of Service (ToS) field is a 1-byte value with these bit fields: - Bits 7:5: DSCP high (3 bits) - Bits 4:2: DSCP low (3 bits) - Bit 1: ECN bit 0 - Bit 0: ECN bit 1

Write NASM code to: (a) Extract the full DSCP value (bits 7:2, shifted to bits 5:0) from AL (b) Set the ECN bits to 0b11 (both bits 1 and 0) without modifying DSCP (c) Clear the ECN bits without modifying DSCP

Exercise 19 (Challenge: Gray Code). Gray code is a binary encoding where consecutive values differ in only one bit. The Gray code of N is N XOR (N >> 1). Write:

(a) uint64_t to_gray(uint64_t n) — convert to Gray code (b) uint64_t from_gray(uint64_t g) — convert from Gray code back to binary

For from_gray, the algorithm is:

n = g
n ^= (n >> 32)
n ^= (n >> 16)
n ^= (n >> 8)
n ^= (n >> 4)
n ^= (n >> 2)
n ^= (n >> 1)

Exercise 20 (Challenge: XOR Cipher Optimized). Extend the XOR cipher from the chapter to process 8 bytes at a time using 64-bit XOR. The function signature:

void xor_encrypt_fast(uint8_t *data, size_t len, uint64_t key64)

Where key64 is a pre-replicated key (the 8-byte key byte repeated 8 times). Process complete 8-byte blocks with xor [rdi+...], key64, then handle the tail (0-7 remaining bytes) byte by byte.

Write the complete NASM function.