Bitwise operators (AND, OR, XOR, NOT) in Verilog - Time & Space Complexity

Time Complexity: Bitwise operators (AND, OR, XOR, NOT)

O(n)

Understanding Time Complexity

We want to understand how the time to run bitwise operations changes as the input size grows.

How does the number of bits affect the work done by AND, OR, XOR, and NOT?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module bitwise_ops #(
  parameter int N = 32
) (
  input  logic [N-1:0] a, b,
  output logic [N-1:0] and_out,
  output logic [N-1:0] or_out,
  output logic [N-1:0] xor_out,
  output logic [N-1:0] not_out
);

  assign and_out = a & b;
  assign or_out  = a | b;
  assign xor_out = a ^ b;
  assign not_out = ~a;

endmodule
    

This module performs bitwise AND, OR, XOR, and NOT on two N-bit inputs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise operation on each bit of the input vectors.
• How many times: Once per bit, so N times for inputs of size N.

How Execution Grows With Input

Each bit is processed independently, so the total work grows directly with the number of bits.

Input Size (n)	Approx. Operations
10	10 bitwise operations per operator
100	100 bitwise operations per operator
1000	1000 bitwise operations per operator

Pattern observation: The operations increase linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the bitwise operations grows in direct proportion to the number of bits.

Common Mistake

[X] Wrong: "Bitwise operations take constant time regardless of input size."

[OK] Correct: Each bit must be processed, so more bits mean more work, making time grow with input size.

Interview Connect

Understanding how bitwise operations scale helps you reason about hardware design and low-level code efficiency, a useful skill in many technical discussions.

Self-Check

"What if we used a fixed-size 32-bit input instead of variable size N? How would the time complexity change?"

Practice

1. Which bitwise operator in Verilog flips each bit of a binary number?
~ is the symbol for which operator?

easy

A. XOR

B. NOT

C. OR

D. AND

Solution

1. Step 1: Understand the operator symbol

   The symbol ~ in Verilog is used to flip bits, meaning it changes 0 to 1 and 1 to 0.

2. Step 2: Match symbol to operator name

   This flipping action corresponds to the NOT operator, which inverts each bit.

3. Final Answer:

   NOT -> Option B

4. Quick Check:

   ~ = NOT [OK]

Hint: Remember ~ flips bits, so it's NOT operator [OK]

Common Mistakes:

• Confusing ~ with AND (&)
• Thinking ~ is OR (|)
• Mixing ~ with XOR (^)

2. Which of the following is the correct Verilog syntax for bitwise AND of two 4-bit vectors a and b?

easy

A. assign c = a & b;

B. assign c = a && b;

C. assign c = a | b;

D. assign c = a ^ b;

Solution

1. Step 1: Identify bitwise AND operator

   In Verilog, the bitwise AND operator is &, which works bit by bit on vectors.

2. Step 2: Check syntax correctness

   The syntax assign c = a & b; correctly assigns the bitwise AND of a and b to c.

3. Final Answer:

   assign c = a & b; -> Option A

4. Quick Check:

   & is bitwise AND [OK]

Hint: Use single & for bitwise AND, not && [OK]

Common Mistakes:

• Using && which is logical AND
• Confusing & with | (OR)
• Using ^ which is XOR

3. What is the 4-bit result of the following Verilog expression?
assign result = 4'b1101 ^ 4'b1011;

medium

A. 4'b1000

B. 4'b1110

C. 4'b0110

D. 4'b0010

Solution

1. Step 1: Understand XOR operation

   XOR (^) compares bits: if bits differ, result is 1; if same, result is 0.

2. Step 2: Calculate bitwise XOR

   Bits: 1101 ^ 1011
   1 ^ 1 = 0
   1 ^ 0 = 1
   0 ^ 1 = 1
   1 ^ 1 = 0
   Result = 0110

3. Final Answer:

   4'b0110 -> Option C

4. Quick Check:

   1101 ^ 1011 = 0110 [OK]

Hint: XOR gives 1 only if bits differ [OK]

Common Mistakes:

• Mixing XOR with OR or AND results
• Calculating bits incorrectly
• Confusing bit order

4. Identify the error in this Verilog code snippet:

assign out = a |& b;

where a and b are 4-bit vectors.

medium

A. Should use logical OR || instead

B. Missing semicolon at the end

C. Vectors a and b must be single bits

D. Operator |& is invalid for bitwise operations

Solution

1. Step 1: Check operator validity

   The operator |& is not a valid bitwise operator in Verilog; it is a reduction operator but used incorrectly here.

2. Step 2: Understand correct bitwise OR usage

   For bitwise OR between vectors, use | alone, like a | b.

3. Final Answer:

   Operator |& is invalid for bitwise operations -> Option D

4. Quick Check:

   |& is invalid here [OK]

Hint: Use single | for bitwise OR, not |& [OK]

Common Mistakes:

• Confusing reduction and bitwise operators
• Forgetting semicolon (though present here)
• Using logical OR || instead of bitwise |

5. Given two 4-bit vectors a = 4'b1010 and b = 4'b1100, which Verilog expression produces a 4-bit vector where bits are set to 1 only if the corresponding bits in a and b differ?

hard

A. assign c = a ^ b;

B. assign c = a & b;

C. assign c = a | b;

D. assign c = ~a;

Solution

1. Step 1: Understand the requirement

   We want bits set to 1 only where a and b differ.

2. Step 2: Identify operator for differing bits

   The XOR operator (^) sets bits to 1 where bits differ and 0 where they are the same.

3. Step 3: Apply XOR to given vectors

   For a = 1010 and b = 1100, a ^ b = 0110, which matches the requirement.

4. Final Answer:

   assign c = a ^ b; -> Option A

5. Quick Check:

   XOR gives 1 for differing bits [OK]

Hint: Use XOR (^) to find differing bits [OK]

Common Mistakes:

• Using AND (&) which gives common bits
• Using OR (|) which sets bits if either is 1
• Using NOT (~) which flips all bits