Logical operators in Verilog - Time & Space Complexity

Time Complexity: Bitwise operators

O(n)

Understanding Time Complexity

Bitwise operators in Verilog combine or compare signals to produce true or false results.

We want to see how the time to evaluate these operators changes as input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module logic_ops(input wire [7:0] a, b, output wire [7:0] result);
  assign result = (a & b) | (~a & b) | (a & ~b);
endmodule
    

This code uses bitwise AND, OR, and NOT operators on 8-bit inputs to produce an 8-bit output.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise logical operations on each bit of the 8-bit inputs.
• How many times: 8 times, once per bit in the input vectors.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n bits)	Approx. Operations
8	24 bitwise operations
16	48 bitwise operations
32	96 bitwise operations

Pattern observation: The number of operations grows directly with the number of bits.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows linearly as the input size increases.

Common Mistake

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

[OK] Correct: Each bit in the input must be processed, so more bits mean more operations and more time.

Interview Connect

Understanding how logical operations scale helps you reason about hardware design and signal processing efficiency.

Self-Check

"What if we changed the inputs from 8-bit vectors to 2D arrays of bits? How would the time complexity change?"

Practice

1. Which logical operator in Verilog returns true only if both operands are true?

easy

A. ^ (XOR)

B. || (OR)

C. ! (NOT)

D. && (AND)

Solution

1. Step 1: Understand the AND operator

   The AND operator (&&) returns true only when both inputs are true.

2. Step 2: Compare with other operators

   OR (||) returns true if at least one input is true, NOT (!) inverts the input, XOR (^) returns true if inputs differ.

3. Final Answer:

   && (AND) -> Option D

4. Quick Check:

   AND needs both true = && [OK]

Hint: AND needs both true inputs to be true [OK]

Common Mistakes:

• Confusing OR (||) with AND (&&)
• Thinking NOT (!) is a binary operator
• Mixing XOR (^) with AND (&&)

2. Which of the following is the correct syntax for the logical OR operator in Verilog?

easy

A. |

B. ||

C. &

D. &&

Solution

1. Step 1: Identify logical OR syntax

   Logical OR in Verilog is represented by double vertical bars: ||.

2. Step 2: Differentiate from bitwise OR

   Single | is bitwise OR, && is logical AND, & is bitwise AND.

3. Final Answer:

   || -> Option B

4. Quick Check:

   Logical OR = || [OK]

Hint: Logical OR uses double vertical bars || [OK]

Common Mistakes:

• Using single | instead of || for logical OR
• Confusing bitwise and logical operators
• Using && instead of ||

3. What is the output of this Verilog expression if a = 1'b0 and b = 1'b1?
assign result = !(a && b) || a;

medium

A. 1'b0

B. Z (high impedance)

C. 1'b1

D. X (unknown)

Solution

1. Step 1: Evaluate inner AND (a && b)

   a = 0, b = 1, so a && b = 0 (false).

2. Step 2: Apply NOT and OR

   !(0) = 1, then 1 || 0 = 1 (true).

3. Final Answer:

   1'b1 -> Option C

4. Quick Check:

   !(0) || 0 = 1 [OK]

Hint: Evaluate inner && first, then apply ! and || [OK]

Common Mistakes:

• Forgetting NOT (!) flips the value
• Evaluating OR before AND
• Confusing 1'b0 and 1'b1 values

4. Identify the error in this Verilog code snippet:

wire a, b, c;
assign c = a &| b;

medium

A. Incorrect use of &| operator

B. Missing semicolon after wire declaration

C. Using assign instead of always block

D. No error, code is correct

Solution

1. Step 1: Check operator syntax

   The operator &| does not exist in Verilog; bitwise AND is & and bitwise OR is |.

2. Step 2: Confirm correct operator usage

   To combine signals logically, use && or ||; for bitwise, use & or | separately.

3. Final Answer:

   Incorrect use of &| operator -> Option A

4. Quick Check:

   No &| operator in Verilog [OK]

Hint: Check operator symbols carefully; &| is invalid [OK]

Common Mistakes:

• Assuming &| is a valid operator
• Ignoring operator precedence
• Confusing bitwise and logical operators

5. Given inputs a, b, and c, which Verilog expression correctly implements the logic: "Output is true if either a and b are both true, or c is false"?

hard

A. assign out = (a && b) || !c;

B. assign out = !(a && b) || c;

C. assign out = (a || b) && !c;

D. assign out = !(a || b) && c;

Solution

1. Step 1: Translate the condition to logic

   Output is true if (a AND b) is true OR c is false (NOT c).

2. Step 2: Match expression with condition

   assign out = (a && b) || !c; uses (a && b) || !c which matches the condition exactly.

3. Final Answer:

   assign out = (a && b) || !c; -> Option A

4. Quick Check:

   AND + OR + NOT combined correctly [OK]

Hint: Translate words to (a && b) || !c quickly [OK]

Common Mistakes:

• Mixing OR and AND order
• Forgetting to negate c
• Using bitwise instead of logical operators