Is This Number a Power of Two

Where the interviewer goes next. Open a node to practise that follow-up.

WhyWhat IfBreak ItCompare

1. Is This Number a Power of Two
2. Break ItThe Signed Input That Passed as a Power of TwoL0 FresherL1 Junior

   Asked if the input could be signed

   The input is now an 8-bit signed value, kept in 8 bits. Which input breaks the check?

   logic signed [7:0] m;
   m = x - 8'sd1;
   return x != 0 && (x & m) == 0;

   Reveal the Model Answer

   -128 breaks it. Its pattern is 1000_0000, one bit set. In 8 bits, -128 - 1 wraps to 127, so the AND is zero. Check x > 0 instead of x != 0.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 -128 breaks it. Key point 2 Its pattern is 1000_0000, one bit set. Key point 3 In 8 bits, -128 - 1 wraps to 127, so the AND is zero. Key point 4 Check x > 0 instead of x != 0.

   Missed Corner

   "The trick works for any integer."

   It tests for one bit set. In two's complement the most negative value also has one bit set. The twin reports -128 as a power of two.

   Run It

   Every 8-bit signed value through the unsigned-style check.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: is_pow2(-128) = 1, 8 values accepted FAIL: -128 is 8'b1000_0000, one bit set, so the unsigned test calls it a power of two

   See the Fix

   module tb;
     // An 8-bit signed datapath: x - 1 is kept in 8 bits, as a register would keep it.
     function automatic bit is_pow2(input logic signed [7:0] x);
       logic signed [7:0] m;
       m = x - 8'sd1;
       return x > 0 && (x & m) == 0;
     endfunction
     int n = 0;
     initial begin
       for (int v = -128; v < 128; v++) if (is_pow2(v)) n++;
       $display("is_pow2(-128) = %0d, %0d values accepted", is_pow2(-128), n);
       if (!is_pow2(-128) && n == 7) $display("PASS: x > 0 keeps out -128; 1 to 64 are the seven powers of two");
     end
   endmodule
   

   Prints: PASS: x > 0 keeps out -128; 1 to 64 are the seven powers of two

   • Lesson R1.4Widths, Truncation and Sign
3. CompareCounting the Ones in a WordL0 FresherL1 Junior

   Count the set bits in a byte. Compare a bit-by-bit loop with the x & (x - 1) trick.

   Reveal the Model Answer

   The loop looks at all 8 bits every time. The trick clears one 1 per step, so it takes as many steps as there are ones. In software, that saves time for sparse words. In hardware, the fixed 8-step loop unrolls to a popcount tree. The clear-lowest loop must be bounded to 8 steps before synthesis; it then gives similar logic, not fewer steps.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: x=00 loop: 0 ones in 8 steps clear-lowest: 0 ones in 0 steps x=b4 loop: 4 ones in 8 steps clear-lowest: 4 ones in 4 steps x=ff loop: 8 ones in 8 steps clear-lowest: 8 ones in 8 steps

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 The loop looks at all 8 bits every time. Key point 2 The trick clears one 1 per step, so it takes as many steps as there are ones. Key point 3 In software, that saves time for sparse words. Key point 4 In hardware, the fixed 8-step loop unrolls to a popcount tree. Key point 5 The clear-lowest loop must be bounded to 8 steps before synthesis; it then gives similar logic, not fewer steps.

   Misconception

   "The while version is faster in hardware too."

   A synthesizable loop must have a fixed bound, and synthesis unrolls it into one cycle of logic. The step count is a software idea.

   Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 6.3.1.1 Static loops versus data-dependent loops

4. WhyWhy x & (x - 1) Clears the Lowest OneL0 Fresher

   Why does x & (x - 1) clear the lowest set bit?

   Reveal the Model Answer

   Subtracting 1 borrows from the lowest 1. That bit becomes 0 and every 0 below it becomes 1. Bits above it do not change. ANDing with x keeps the upper bits and zeroes the rest.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: x = 00101000 x - 1 = 00100111 x & (x-1) = 00100000

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Subtracting 1 borrows from the lowest 1. Key point 2 That bit becomes 0 and every 0 below it becomes 1. Key point 3 Bits above it do not change. Key point 4 ANDing with x keeps the upper bits and zeroes the rest.
5. What IfBinary to Gray Code and BackL0 FresherL1 Junior

   What if the next puzzle is Gray code? Convert binary to Gray and back.

   Reveal the Model Answer

   Binary to Gray is g = b ^ (b >> 1). The way back is not the same formula. Each binary bit is the XOR of all the Gray bits at and above it. Consecutive Gray values differ in one bit, including the wrap from 15 to 0.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: gray of 0..7: 0000 0001 0011 0010 0110 0111 0101 0100 16 of 16 steps change one bit; 0 of 16 round trips wrong PASS: binary to Gray and back for all 16 values

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Binary to Gray is g = b ^ (b >> 1). Key point 2 The way back is not the same formula. Key point 3 Each binary bit is the XOR of all the Gray bits at and above it. Key point 4 Consecutive Gray values differ in one bit, including the wrap from 15 to 0.

   Misconception

   Uses g ^ (g >> 1) to convert back.

   Each binary bit depends on every Gray bit above it, not only its neighbour. The twin gets most round trips wrong.

   Run It

   The round trip with the forward formula used backwards.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: FAIL: g ^ (g >> 1) does not undo the Gray code; the inverse needs an XOR of all higher bits

   See the Fix

   module tb;
     function automatic logic [3:0] to_gray(input logic [3:0] b);
       return b ^ (b >> 1);
     endfunction
     function automatic logic [3:0] from_gray(input logic [3:0] g);
       logic [3:0] b;
       b[3] = g[3];
       for (int i = 2; i >= 0; i--) b[i] = b[i+1] ^ g[i];   // each bit is the XOR of all Gray bits above it
       return b;
     endfunction
     int bad = 0, onebit = 0;
     logic [3:0] diff;
     initial begin
       for (int v = 0; v < 16; v++) begin
         if (from_gray(to_gray(v)) !== v[3:0]) bad++;
         diff = to_gray(v[3:0]) ^ to_gray(v[3:0] + 4'd1);   // includes 15 -> 0
         if (diff[0] + diff[1] + diff[2] + diff[3] == 1) onebit++;
       end
       $display("gray of 0..7: %b %b %b %b %b %b %b %b", to_gray(0), to_gray(1), to_gray(2), to_gray(3), to_gray(4), to_gray(5), to_gray(6), to_gray(7));
       $display("%0d of 16 steps change one bit; %0d of 16 round trips wrong", onebit, bad);
       if (bad == 0) $display("PASS: binary to Gray and back for all 16 values");
     end
   endmodule
   

   Prints: PASS: binary to Gray and back for all 16 values

   • Lesson R6.4Gray Codes and the Asynchronous FIFO
   • Problem R6.4.1A Gray Pointer