Bitwise and Reduction Operators

The last article separated & from &&. This one is about & and its relatives properly: the bitwise operators that work on corresponding bits of two vectors, and the reduction operators that work across all the bits of one vector. Both families are the plain gates of Module 1, AND, OR, XOR and their complements, arranged one of two ways.

Bitwise

wire [7:0] a = 8'b1010_1010;
wire [7:0] b = 8'b1100_1100;

wire [7:0] band  = a & b;       // 8'b1000_1000
wire [7:0] bor   = a | b;       // 8'b1110_1110
wire [7:0] bxor  = a ^ b;       // 8'b0110_0110
wire [7:0] bxnor = a ~^ b;      // 8'b1001_1001
wire [7:0] bnot  = ~a;          // 8'b0101_0101
wire [7:0] bnand = ~(a & b);    // 8'b0111_0111
wire [7:0] bnor  = ~(a | b);    // 8'b0001_0001

Each bit position is independent: eight AND gates side by side, no carry, no interaction. A bitwise operation on 64 bits takes exactly as long as on 1 bit.

Four idioms cover most of what bitwise operators are used for:

wire [7:0] lower_nibble = data & 8'h0F;      // mask: keep some bits, zero the rest
wire [7:0] bit7_set     = data | 8'h80;      // set: force chosen bits to 1
wire [7:0] bit0_flip    = data ^ 8'h01;      // toggle: invert chosen bits
wire [7:0] lower_clear  = data & ~(8'h0F);   // clear: force chosen bits to 0

The ~(8'h0F) in the last line is a constant, evaluated when the design is elaborated, so no inverter is built; the cost is one AND gate per bit.

Reduction

A reduction operator is the same symbol used as a prefix on a single vector. It combines all the bits and gives one bit:

wire [7:0] data = 8'b1010_0101;

wire and_all  = &data;     // 1 if every bit is 1: 0
wire nand_all = ~&data;    // 1 if any bit is 0: 1
wire or_all   = |data;     // 1 if any bit is 1: 1
wire nor_all  = ~|data;    // 1 if every bit is 0: 0
wire xor_all  = ^data;     // 1 if an odd number of bits are 1: 0
wire xnor_all = ~^data;    // 1 if an even number of bits are 1: 1

^data is $d_7 \oplus d_6 \oplus \cdots \oplus d_0$, and the synthesiser builds it as a balanced tree, $\lceil \log_2 N \rceil$ levels deep: three XOR delays for a byte, six for a 64-bit word.

The zero flag of an ALU can be written either way:

wire zero_a = (result == 8'h00);
wire zero_b = ~|result;

They synthesise to the same thing, a NOR tree. The reduction form says what it is.

A parity generator

Even parity appends a bit that makes the total number of ones even; odd parity makes it odd. The receiver recomputes and compares. The whole generator is one reduction:

`timescale 1ns / 1ps
`default_nettype none

module parity_gen #(
    parameter WIDTH = 8
)(
    input  wire [WIDTH-1:0] data,
    output wire             parity_even,   // makes the total count of ones even
    output wire             parity_odd     // makes it odd
);

    assign parity_even = ^data;    // 1 when data has an odd number of ones, so the total becomes even
    assign parity_odd  = ~^data;   // the complement

endmodule

The naming trips people up, so read the two lines slowly. ^data is 1 when the data has an odd number of ones. For even parity the total, data plus parity bit, must be even, so the bit is 1 exactly when the data is odd: ^data. Odd parity is the complement. The generator is a balanced XOR tree, purely combinational, and it is the circuit in a UART, in ECC memory, and at the bottom of every CRC.

Hardware summary

No clocks, no registers; the delay is the tree depth times a gate delay.

Practice Exercise

Write a 4-bit equality comparator using only bitwise and reduction operators, no ==.

`timescale 1ns / 1ps
`default_nettype none

module comparator_4bit (
    input  wire [3:0] a,
    input  wire [3:0] b,
    output wire       eq
);
    wire [3:0] diff = a ^ b;    // a bit is 0 where a and b match
    assign eq = ~|diff;         // all match when no bit of diff is set
endmodule

The next article moves bits around rather than combining them: shifts, and concatenation and replication used as tools in their own right.