Lab: Bit Manipulation¶

Overview¶

This hands-on lab session marks the transition from RISC-V assembly to RISC-V machine code. Before we can decode 32-bit instruction words by hand and in C, we need fluency with the bitwise operators. The session opens with Project03 interactive grading (IG) logistics and a careful diagram of the famous rstr null-terminator bug, then steps back to the course "big picture" before drilling into the core skill: manipulating individual bits with ~, &, |, ^, and the three shift operators (SLL, SRL, SRA) in both C and RISC-V. Work each example by hand in binary — by the end of the semester these truth tables and shift behaviors should be automatic.

Learning Objectives¶

Trace the rstr (reverse-string) bug and explain why it accidentally "worked" because of an adjacent string's null terminator
Place this lab in the course arc: data representation → assembly → machine code → emulator
Distinguish bitwise operators (~ & | ^ << >>) from relational/logical operators (&& || !)
Recall the truth tables for AND, OR, XOR, and NOT from memory
Convert between binary and decimal using bit positions and place values in a byte and a 32-bit word
Apply Shift Left Logical (SLL), Shift Right Logical (SRL), and Shift Right Arithmetic (SRA), and predict the fill bits
Connect arithmetic shifts to two's complement and signed division by powers of two
Map each C bitwise operator to its RISC-V instruction (and/andi, or/ori, xor/xori, sll/slli, srl/srli, sra/srai)

Prerequisites¶

Number bases: binary, decimal, hexadecimal, and the 0b/0x C literal prefixes (Lab04, Project01)
Two's complement representation of signed integers (Project03)
C fundamentals: uint8_t/uint32_t/int32_t types, arrays, strings, pointers (Project01)
RISC-V assembly basics: registers, instructions, function calling conventions (Lab02, Project02, Project03)
The argv/argc layout in memory (Project01)

1. Project03 Interactive Grading (IG)¶

Project03 was graded interactively: you sit with a grader, run your code, and explain it. The point is not to catch you — it is to confirm you understand the code you submitted.

TAs grade most students; the instructor reviews for consistency and fairness.
Using AI tools (ChatGPT, Copilot, etc.) is allowed, but you must be able to explain every line. During IG you will be asked:
- Design decisions — "Why did you do it this way?"
- Implementation walk-through — "Show me how rstr_rec works."
- Debugging — "What problems did you hit, and how did you find them?"
- Tooling — terminal editing (micro/vim) and single-stepping with gdb.
For Project04, a different group of students grades with the instructor, so everyone gets direct instructor interaction over the term.

The Project03 rubric (see /assignments/project03/) is 80 points automated tests + 20 points IG questions. The takeaway for this lab: be ready to reason about your code at the bit and byte level, which is exactly the skill we sharpen below.

2. The `rstr` Null-Terminator Bug¶

One of the most instructive moments of the session was diagramming a subtle bug in the reverse-string function. The function appeared to work for years, but only by accident.

What `rstr` is supposed to do¶

Reverse a C string from a source buffer src into a destination buffer dst. Recall a C string is an array of char terminated by a null byte '\0' (value 0).

// Reverse src into dst. len = strlen(src).
void rstr(char *dst, char *src, int len) {
    int s = len - 1;   // last real character of src
    int d = 0;         // first slot of dst
    while (/* ??? termination condition ??? */) {
        dst[d] = src[s];
        d = d + 1;
        s = s - 1;
    }
    dst[d] = '\0';     // terminate dst
}

For src = "FooBar", len = 6, indices are:

src:  f  o  o  B  a  r  \0
idx:  0  1  2  3  4  5   6     (the \0 lives at index 6 = len)

We copy src[5]='r' → dst[0], src[4]='a' → dst[1], and so on, walking s down toward 0.

The diagram from class¶

dst:  | r | a | B | o | o | f |     <- being filled left-to-right
        ^   ^   ^
        d=0 d=1 d=2 ...

src:  | f | o | o | B | a | r | \0 |
idx:    0   1   2   3   4   5    6
                              ^ start here (s = len-1 = 5)
                              walk s downward: 5,4,3,2,1,0
len = 6

The bug¶

The buggy termination condition tested for the source's null terminator while scanning downward:

while (src[s] != '\0') { ... }   // WRONG when walking backward

Walking backward from index len-1, you never hit src's own '\0' (it sits at index len, which you started past). So what stops the loop? When s decrements below 0, src[s] reads memory before src. Often that adjacent memory happens to be the null terminator of a previously stored string (e.g., another argv entry), so the loop coincidentally stops — but this is undefined behavior and depends entirely on memory layout.

Why adjacent strings matter — the `argv` picture¶

Command-line argument strings are packed contiguously in memory. For ./foo bar, the bytes for "foo" and "bar" sit next to each other, each with its own '\0'. A red brace in the notes highlighted that src points into this packed region, and the '\0' that "accidentally" stopped the loop belonged to a neighboring string.

high addr
          | \0 |
          | r  |  <-+
          | a  |    | "bar"  (src points here)
          | b  |  <-+
          | \0 |  <- the null that "accidentally" stops a backward scan
          | o  |  <-+
          | o  |    | "foo"
          | f  |  <-+
          | ...|
argv[2]   |    |
argv[1]   |    |
argv[0]   |    |
low addr

The correct fix¶

Do not rely on memory you do not own. Stop when the source index goes below zero:

void rstr(char *dst, char *src, int len) {
    int s = len - 1;
    int d = 0;
    while (s >= 0) {        // CORRECT: stop when we run off the front
        dst[d] = src[s];
        d = d + 1;
        s = s - 1;
    }
    dst[d] = '\0';          // always terminate the destination
}

Exam tip from class: understand both the bug and the fix pattern. The lesson generalizes — never let a loop read memory it has no guaranteed claim to, and choose a termination condition based on your own indices, not on incidental neighboring data.

3. Big Picture — Where This Lab Fits¶

Greg sketched the course as two converging tracks. The left track is the software/representation track; the right track is the hardware track. They meet at the machine.

flowchart TD
    C["C / Data Representation"] --> ASM["RISC-V Assembly"]
    ASM --> MC["RISC-V Machine Code (rv_emu)"]
    DD["Digital Design"] --> PD["Processor Design"]
    MC --> PD
    style MC fill:#f9f,stroke:#333,stroke-width:2px

We have covered data representation (bases, two's complement) and RISC-V assembly (Projects 02–03).
Next we move to RISC-V machine code: 32-bit instruction words that we will decode and execute in software. That software is rv_emu, an emulator written in C.
On the hardware side, digital design leads to processor design — eventually you run the same machine code on a processor you helped design.

Why bits now? Decoding a machine instruction means slicing a 32-bit word into fields (opcode, rd, rs1, funct3, …). That is pure bit manipulation: shift the field down, then mask off the bits you do not want. Master the operators here and the emulator becomes straightforward.

4. Bitwise vs. Relational Operators¶

A common source of bugs: confusing & with &&, or | with ||. They are different operators with different jobs.

Category	C operators	What they do	Operate on
Bitwise	`~` `&` `\\|` `^` `<<` `>>`	Manipulate individual bits, position by position	Whole bit patterns
Relational / Logical	`&&` `\\|\\|` `!` `==` `<` `>`	Produce a true/false (0/1) result for control flow	Truth values

The class table contrasted them side by side:

   bitwise ops              relational / logical
   ~   (not)                &&   and
   >>  right shift          ||   or
   <<  left shift           !    not
   &   and
   |   or
   ^   xor

Rule of thumb:

Use bitwise when you care about the bits: masking, packing, decoding instructions.
Use logical when you care about a condition: if (x && y).

// Bitwise: result is a bit pattern
uint8_t flags = 0b1100;
uint8_t mask  = 0b0100;
uint8_t bit   = flags & mask;   // 0b0100 (the bit, in place)

// Logical: result is 0 or 1
int ready = (count > 0) && (error == 0);   // 1 if both true

5. Binary, Bytes, and Words¶

The two values of a bit¶

A single bit is either 0 or 1. These two states go by many names; learn to read all of them:

`0`	`1`
false	true
unset / clear	set
low	high
off	on

A byte = 8 bits¶

Bits within a byte are numbered 7 (most significant) down to 0 (least significant). Each position has a place value that is a power of two.

bit:   7    6    5    4    3    2    1    0
       1    1    0    1    1    0    0    1
value:128  64   32   16   8    4    2    1
       ^                                  ^
   most significant                   least significant
   bit (MSB)                          bit (LSB)

Converting that byte to decimal — add the place values where the bit is 1:

128 + 64 + 16 + 8 + 1 = 217

So 0b11011001 = 217.

A word = 4 bytes = 32 bits¶

A 32-bit value (a "word") is four bytes laid out from bit 31 down to bit 0. Knowing the byte boundaries is essential for instruction decoding.

 31      24 23      16 15       8 7        0
|  byte 3  |  byte 2  |  byte 1  |  byte 0  |

Byte	Bit range
byte 3	31–24
byte 2	23–16
byte 1	15–8
byte 0	7–0

This layout is exactly how we will carve a 32-bit RISC-V instruction word into fields later.

6. The Four Bitwise Logical Operators¶

Each operator is applied positionally: bit i of the result depends only on bit i of the inputs. Memorize these truth tables — they are with you for the rest of the semester.

AND (`&`)¶

1 only when both inputs are 1.

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

OR (`|`) — inclusive or¶

1 when either input is 1.

a	b	a \| b
0	0	0
0	1	1
1	0	1
1	1	1

XOR (`^`) — exclusive or¶

1 when the inputs differ.

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

Useful XOR identities: a ^ a = 0, a ^ 0 = a, and a ^ 0xFF flips all 8 bits (a cheap NOT for a byte).

NOT (`~`) — bitwise complement¶

Inverts every bit. (This is unary — one operand.)

a	~a
0	1
1	0

Watch the distinction: ~ is bitwise NOT (flips all bits); ! is logical NOT (turns nonzero into 0, and 0 into 1).

Worked example (from class)¶

Declare two bytes and compute all four operators:

uint8_t a, b;
a = 0b11001010;   // 0xCA = 202
b = 0b10011001;   // 0x99 = 153

AND — keep a 1 only where both have a 1:

  a    = 1 1 0 0 1 0 1 0
  b    = 1 0 0 1 1 0 0 1
  -----------------------
  a&b  = 1 0 0 0 1 0 0 0     (0x88)

NOT of a — flip every bit:

  a    = 1 1 0 0 1 0 1 0
  ~a   = 0 0 1 1 0 1 0 1     (0x35)

OR — a 1 where either has a 1:

  a    = 1 1 0 0 1 0 1 0
  b    = 1 0 0 1 1 0 0 1
  -----------------------
  a|b  = 1 1 0 1 1 0 1 1     (0xDB)

XOR — a 1 only where they differ:

  a    = 1 1 0 0 1 0 1 0
  b    = 1 0 0 1 1 0 0 1
  -----------------------
  a^b  = 0 1 0 1 0 0 1 1     (0x53)

Running C confirms it:

#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint8_t a = 0b11001010;   // 202
    uint8_t b = 0b10011001;   // 153
    printf("a&b = 0x%02X\n", a & b);   // 0x88
    printf("~a  = 0x%02X\n", (uint8_t)~a); // 0x35
    printf("a|b = 0x%02X\n", a | b);   // 0xDB
    printf("a^b = 0x%02X\n", a ^ b);   // 0x53
    return 0;
}

RISC-V equivalents¶

Each operator maps to a register-register instruction (R-type) and, where it makes sense, an immediate form (I-type):

C operator	RISC-V (reg)	RISC-V (immediate)
`&`	`and rd, rs1, rs2`	`andi rd, rs1, imm`
`\\|`	`or rd, rs1, rs2`	`ori rd, rs1, imm`
`^`	`xor rd, rs1, rs2`	`xori rd, rs1, imm`
`~x`	—	`xori rd, rs1, -1` (flip all bits)

# uint64_t r = a & b;   a in a0, b in a1, result in a0
and  a0, a0, a1
ret

# uint64_t r = ~a;      a in a0
xori a0, a0, -1     # XOR with all-ones inverts every bit
ret

RISC-V has no dedicated NOT instruction; not rd, rs is a pseudo-instruction the assembler expands to xori rd, rs, -1.

7. Shift Operations¶

Shifting moves every bit left or right by a fixed number of positions. The two operands are the value to shift and the shift amount.

   a  <<  2
   ^      ^
 value  shift amount

There are three shifts. The difference is entirely in what fills the vacated bits.

SLL — Shift Left Logical (`<<`)¶

Bits move toward the MSB. Vacated low bits are filled with 0; bits that fall off the left are discarded.

a      = 0b 1 1 0 0 1 0 1 0      (0xCA)
                \  \  \  \           bits move left by 2
a << 2 = 0b 0 0 1 0 1 0 0 0      (0x28)
                          ^ ^
                          new zeros on the right

Effect: multiply an unsigned value by 2^n. (Bits shifted off the top are lost, so this can overflow.)

SRL — Shift Right Logical (`>>` on unsigned)¶

Bits move toward the LSB. Vacated high bits are filled with 0; bits that fall off the right are discarded.

a      = 0b 1 1 0 0 1 0 1 0      (0xCA)
              /  /  /  /              bits move right by 2
a >> 2 = 0b 0 0 1 1 0 0 1 0      (0x32)
            ^ ^
            new zeros on the left

Effect: unsigned divide by 2^n (the discarded low bits are the remainder).

SRA — Shift Right Arithmetic (`>>` on signed)¶

Same as SRL, except the vacated high bits are filled with copies of the original sign bit (the MSB), preserving the number's sign.

Interpret a as a signed int8_t. Its MSB is 1, so it is negative:

a = 0b11001010  as int8_t = -54

Arithmetic shift right by 2 — fill the top with the sign bit (1):

a       = 0b 1 1 0 0 1 0 1 0      (-54)
a >> 2  = 0b 1 1 1 1 0 0 1 0      (-14)
            ^ ^
            copies of the sign bit (1)

Effect: signed divide by 2^n, rounding toward negative infinity. Note -54 / 4 = -13.5, and SRA gives -14 (rounds down), whereas C's integer division / rounds toward zero and would give -13. This rounding difference matters.

We can verify the SRA result is -14 using two's complement (negate by invert + 1):

result  = 1 1 1 1 0 0 1 0
invert  = 0 0 0 0 1 1 0 1
add 1   = 0 0 0 0 1 1 1 0   = 8 + 4 + 2 = 14
so result = -14   ✓

And the original a = -54:

a       = 1 1 0 0 1 0 1 0
invert  = 0 0 1 1 0 1 0 1
add 1   = 0 0 1 1 0 1 1 0   = 32 + 16 + 4 + 2 = 54
so a = -54   ✓

Picking the right shift in C¶

The shift you get from >> in C depends on the type of the value:

uint8_t  u = 0b11001010;   // unsigned
int8_t   s = 0b11001010;   // signed (= -54)

u >> 2;   // SRL (logical): 0b00110010 = 50
s >> 2;   // SRA (arithmetic): 0b11110010 = -14

Unsigned type → >> is logical (SRL).
Signed type → >> is arithmetic (SRA) on every mainstream compiler. (The C standard technically leaves signed >> implementation-defined, but in practice it is arithmetic; conceptually it preserves the sign.)
<< is always logical (fills with 0). Left-shifting a negative signed value is undefined behavior in C — shift unsigned types when you mean to manipulate bits.

Comparison table¶

Operation	Direction	Vacated bits filled with	Effect	RISC-V
SLL `<<`	left	`0` (on the right)	multiply by `2^n`	`sll`, `slli`
SRL `>>` (unsigned)	right	`0` (on the left)	unsigned divide by `2^n`	`srl`, `srli`
SRA `>>` (signed)	right	sign bit (on the left)	signed divide by `2^n`	`sra`, `srai`

RISC-V shift instructions¶

slli a0, a0, 2     # a0 = a0 << 2   (shift amount is an immediate)
srli a0, a0, 2     # a0 = a0 >> 2   logical
srai a0, a0, 2     # a0 = a0 >> 2   arithmetic (sign-preserving)

sll  a0, a1, a2    # a0 = a1 << a2  (shift amount in a register)

Hardware aside from class: shifts are implemented with a barrel shifter, a block of digital logic that can shift by any amount in a single step — no looping over one-bit shifts.

8. Masking — Extracting Bit Fields¶

The reason we care so much about shifts and AND is decoding. To pull a field out of a larger word you combine two steps:

Shift the field down so it starts at bit 0.
Mask with AND to zero out everything above the field.

The mask for the low w bits is (1 << w) - 1:

`w`	`(1 << w) - 1`	binary	hex
1	1	`0000 0001`	`0x01`
3	7	`0000 0111`	`0x07`
4	15	`0000 1111`	`0x0F`
7	127	`0111 1111`	`0x7F`
8	255	`1111 1111`	`0xFF`

Example: extract the middle 4 bits (bits 2–5) of a byte¶

uint8_t  x = 0b11011010;
uint32_t v = x >> 2;        // shift bits 2..5 down to 0..3 -> 0b00110110
v = v & 0b1111;             // mask off everything above bit 3 -> 0b0110 = 6

x        = 1 1 0 1 1 0 1 0
x >> 2   = 0 0 1 1 0 1 1 0      bits 2-5 are now in positions 0-3
& 0b1111 = 0 0 0 0 0 1 1 0      = 0x6

This is exactly the get_bits(iw, start, count) pattern you will write for the emulator: shift the instruction word right by the field's start bit, then AND with a count-bit mask. Looking ahead (Lab03/Project04), an R-type instruction word is sliced this way:

| funct7 [31:25] | rs2 [24:20] | rs1 [19:15] | funct3 [14:12] | rd [11:7] | opcode [6:0] |

To get rd (bits 11–7): (iw >> 7) & 0b11111.

Building values: shift + OR¶

The inverse of extraction is assembly of a value from pieces — shift each piece into position and OR them together. (You will do this when reconstructing branch/jump immediates from their scattered bits.)

uint32_t imm = (hi << 5) | lo;   // place hi above lo, then merge

Sign extension with shifts¶

To sign-extend a narrow two's complement value to 32 bits, shift it fully left so its sign bit lands in bit 31, then arithmetic-shift it back. The SRA fill replicates the sign bit across the upper bits:

int32_t v = 0b1110;        // -2 as a 4-bit two's complement value
v = (v << 28) >> 28;       // -> 0xFFFFFFFE = -2 in 32 bits

This trick only works because >> on a signed int32_t is arithmetic.

9. Emulators — Looking Ahead¶

The session closed by defining the destination of this whole bit-manipulation effort.

An emulator is software that simulates the behavior of hardware. rv_emu is a RISC-V emulator written in C that executes RISC-V machine code.
The emulator holds the processor state in a struct:

#define NREGS       32
#define STACK_SIZE  8192

struct rv_state {
    uint64_t regs[NREGS];     // x0..x31
    uint64_t pc;              // program counter
    uint8_t  stack[STACK_SIZE];
};

The fetch-decode-execute cycle is bit manipulation end to end:
1. Fetch the 32-bit instruction word: iw = *pc.
2. Decode the opcode (low 7 bits): iw & 0x7F.
3. Dispatch to a handler (emu_r_type, emu_i_type, …) that further slices funct3, funct7, rd, rs1, rs2 with shift + mask.
4. Execute: update regs and/or memory.
5. Advance pc (usually pc += 4).

Every one of those decode steps is the shift-and-mask pattern from Section 8. The next lecture begins decoding real instructions and building the emulator.

Key Concepts¶

Concept	Definition	Example
Bitwise operator	Acts on each bit position independently	`0xCA & 0x99 = 0x88`
Relational/logical operator	Produces a 0/1 truth value for control flow	`(x > 0) && y`
Byte	8 bits, numbered MSB 7 … LSB 0	`0b11011001 = 217`
Word	32 bits = 4 bytes (byte 3 … byte 0)	bits 31–24, 23–16, 15–8, 7–0
AND `&`	`1` only if both bits `1`; used to mask	`0b1010 & 0b1100 = 0b1000`
OR `\\|`	`1` if either bit `1`; used to set bits	`0b1010 \\| 0b0100 = 0b1110`
XOR `^`	`1` if bits differ; used to toggle	`0b1010 ^ 0b1100 = 0b0110`
NOT `~`	Inverts every bit	`~0b11001010 = 0b00110101`
SLL `<<`	Shift left, fill `0`; ×`2^n`	`0xCA << 2 = 0x28`
SRL `>>`	Logical shift right, fill `0`; unsigned ÷`2^n`	`0xCA >> 2 = 0x32`
SRA `>>`	Arithmetic shift right, fill sign bit; signed ÷`2^n`	`(int8_t)0xCA >> 2 = -14`
Mask	`(1 << w) - 1` isolates the low `w` bits	width 4 → `0x0F`
Field extraction	Shift field to bit 0, then AND a mask	`(iw >> 7) & 0x1F` for `rd`
Sign extension	Replicate the sign bit into upper bits	`(v << 28) >> 28`
Emulator	Software that simulates hardware behavior	`rv_emu` runs RISC-V machine code

Practice Problems¶

Problem 1: Apply All Four Logical Operators¶

Given a = 0b10110100 and b = 0b01101100, compute a & b, a | b, a ^ b, and ~a. Give each answer in binary and hex.

Click to reveal solution

a = 1 0 1 1 0 1 0 0   (0xB4)
b = 0 1 1 0 1 1 0 0   (0x6C)

a & b = 0 0 1 0 0 1 0 0   = 0x24   (1 only where both are 1)
a | b = 1 1 1 1 1 1 0 0   = 0xFC   (1 where either is 1)
a ^ b = 1 1 0 1 1 0 0 0   = 0xD8   (1 where they differ)
~a    = 0 1 0 0 1 0 1 1   = 0x4B   (flip every bit)

Problem 2: Logical vs. Bitwise¶

Predict the output of this program and explain the difference between the two computations.

#include <stdio.h>
int main(void) {
    int a = 4;   // 0b100
    int b = 2;   // 0b010
    printf("%d\n", a & b);    // line 1
    printf("%d\n", a && b);   // line 2
    return 0;
}

Click to reveal solution

Line 1 (bitwise AND): 4 & 2
  100
& 010
-----
  000   = 0

Line 2 (logical AND): 4 && 2
  Both operands are nonzero (true), so result is 1.

Output:
0
1

`&` works bit by bit and finds no position where both have a `1`. `&&` only asks "are both operands true (nonzero)?" — they are, so it yields `1`. Confusing the two is a classic bug.

Problem 3: The Three Shifts¶

Let x = 0b10010110. Compute:

x << 1 (logical)
(uint8_t)x >> 2 (logical shift right)
(int8_t)x >> 2 (arithmetic shift right)

Give binary and decimal (signed for part 3).

Click to reveal solution

x = 1 0 0 1 0 1 1 0   (unsigned 150; signed int8 = -106)

1. x << 1:   shift left, fill 0 on right
   0 0 1 0 1 1 0 0   = 0x2C = 44   (top bit fell off; 150*2=300 overflows a byte)

2. (uint8_t)x >> 2:  logical, fill 0 on left
   0 0 1 0 0 1 0 1   = 0x25 = 37   (= 150 / 4, unsigned, truncated)

3. (int8_t)x >> 2:   arithmetic, fill sign bit (1) on left
   1 1 1 0 0 1 0 1   = 0xE5

   Value: invert(1110 0101)=0001 1010, +1 = 0001 1011 = 27, so -27.
   Check: -106 / 4 = -26.5, rounds toward -inf = -27.  ✓

Problem 4: Extract a Bit Field¶

A 32-bit RISC-V instruction word is iw = 0x00A50533. The destination register field rd occupies bits 11–7. Extract rd using shift and mask, and give its value.

Click to reveal solution

iw = 0x00A50533

Step 1 - shift bits 11..7 down to position 0..4:
   rd = iw >> 7

   0x00A50533 = 0000 0000 1010 0101 0000 0101 0011 0011
   >> 7       = 0000 0000 0000 0001 0100 1010 0000 1010

Step 2 - mask the low 5 bits (rd is 5 bits wide):
   mask = (1 << 5) - 1 = 0b11111 = 0x1F
   rd = (iw >> 7) & 0x1F

   ...0000 1010
 & ...0001 1111
   -----------
   ...0000 1010   = 0x0A = 10

rd = 10  (register x10 = a0)

This is the same shift-then-mask pattern `get_bits(iw, 7, 5)` uses in the emulator.

Problem 5: Set, Clear, and Toggle a Bit¶

Using only bitwise operators and shifts, write C expressions that, for a uint8_t x and a bit position n (0–7):

set bit n to 1
clear bit n to 0
toggle bit n
test whether bit n is 1 (result 0 or 1)

Click to reveal solution

// 1. Set bit n: OR in a 1 at position n
x = x | (1 << n);

// 2. Clear bit n: AND with a mask that has 0 only at position n
x = x & ~(1 << n);

// 3. Toggle bit n: XOR with a 1 at position n
x = x ^ (1 << n);

// 4. Test bit n: shift it down to position 0, mask to one bit
int bit = (x >> n) & 1;

These four idioms — set with `|`, clear with `& ~`, toggle with `^`, test with `>> & 1` — are the everyday vocabulary of bit manipulation.

Problem 6: The `rstr` Termination Condition¶

Here is a backward-copy loop. Identify the bug and give the corrected condition.

void rstr(char *dst, char *src, int len) {
    int s = len - 1, d = 0;
    while (src[s] != '\0') {   // <-- here
        dst[d++] = src[s--];
    }
    dst[d] = '\0';
}

Click to reveal solution

The loop walks `s` **downward** from `len - 1`. The source's own `'\0'` lives at index `len`, which we already started below — so `src[s] != '\0'` never becomes false from `src`'s real terminator. When `s` goes negative, `src[s]` reads memory *before* `src` (undefined behavior). It only "works" when a neighboring string's `'\0'` happens to sit there. **Fix:** terminate based on your own index, not foreign memory:

void rstr(char *dst, char *src, int len) {
    int s = len - 1, d = 0;
    while (s >= 0) {           // stop when we run off the front
        dst[d++] = src[s--];
    }
    dst[d] = '\0';
}

Summary¶

Project03 IG rewards understanding, not just passing tests: you must explain your design, walk through your implementation, and demonstrate debugging — bit-level reasoning is central.
The rstr bug stopped a backward copy on a neighboring string's '\0' (undefined behavior). The correct fix tests s >= 0, relying only on indices you own.
Bit manipulation is the bridge to machine code. Decoding 32-bit instructions for the rv_emu emulator is shift + mask, end to end.
Bitwise (~ & | ^ << >>) and logical (&& || !) operators are different. Bitwise work per-bit on patterns; logical produce 0/1 for control flow. Confusing &/&& is a classic bug.
Memorize the truth tables. AND keeps 1 only when both are 1; OR sets 1 if either is; XOR sets 1 when bits differ; NOT flips every bit.
A byte is 8 bits (7…0); a word is 32 bits (4 bytes). Decimal value is the sum of place values where bits are 1.
Three shifts differ only in their fill bit: SLL fills 0 on the right (×2^n), SRL fills 0 on the left (unsigned ÷2^n), SRA fills the sign bit on the left (signed ÷2^n, rounding toward −∞). In C, >> is logical on unsigned types and arithmetic on signed types.
Masking extracts fields: shift the field down to bit 0, then AND with (1 << w) - 1. Shift-and-OR builds values back up, and (v << k) >> k (signed) sign-extends — the exact toolkit for the upcoming emulator.

Lab: Bit Manipulation¶

Overview¶

Learning Objectives¶

Prerequisites¶

1. Project03 Interactive Grading (IG)¶

2. The rstr Null-Terminator Bug¶

What rstr is supposed to do¶

The diagram from class¶

The bug¶

Why adjacent strings matter — the argv picture¶

The correct fix¶

3. Big Picture — Where This Lab Fits¶

4. Bitwise vs. Relational Operators¶

5. Binary, Bytes, and Words¶

The two values of a bit¶

A byte = 8 bits¶

A word = 4 bytes = 32 bits¶

6. The Four Bitwise Logical Operators¶

AND (&)¶

OR (|) — inclusive or¶

XOR (^) — exclusive or¶

NOT (~) — bitwise complement¶

Worked example (from class)¶

RISC-V equivalents¶

7. Shift Operations¶

SLL — Shift Left Logical (<<)¶

SRL — Shift Right Logical (>> on unsigned)¶

SRA — Shift Right Arithmetic (>> on signed)¶

Picking the right shift in C¶

Comparison table¶

RISC-V shift instructions¶

8. Masking — Extracting Bit Fields¶

Example: extract the middle 4 bits (bits 2–5) of a byte¶

Building values: shift + OR¶

Sign extension with shifts¶

9. Emulators — Looking Ahead¶

Key Concepts¶

Practice Problems¶

Problem 1: Apply All Four Logical Operators¶

Problem 2: Logical vs. Bitwise¶

Problem 3: The Three Shifts¶

Problem 4: Extract a Bit Field¶

Problem 5: Set, Clear, and Toggle a Bit¶

Problem 6: The rstr Termination Condition¶

Further Reading¶

Summary¶

2. The `rstr` Null-Terminator Bug¶

What `rstr` is supposed to do¶

Why adjacent strings matter — the `argv` picture¶

AND (`&`)¶

OR (`|`) — inclusive or¶

XOR (`^`) — exclusive or¶

NOT (`~`) — bitwise complement¶

SLL — Shift Left Logical (`<<`)¶

SRL — Shift Right Logical (`>>` on unsigned)¶

SRA — Shift Right Arithmetic (`>>` on signed)¶

Problem 6: The `rstr` Termination Condition¶