Build a bit-counting comparator using NAND logic gates

Question

A bit-counting comparator (BCC) is a logic circuit that takes some number of counting inputs A1, A2, A3, ..., An as well as inputs B1, B2, B4, B8, ... representing a number. It then returns 1 if the total number of A inputs that are on is greater than the number represented in binary by the B inputs (e.g. B1, B2, and B8 would make the number 11), and 0 otherwise.

For example, for a bit-counting comparator that takes 5 inputs, of which A2, A4, A5, and B2 are set to 1, will return 1 because there are 3 A inputs that are on, which is greater than 2 (the number represented by only B2 being on).

Your task is to create a bit-counting comparator that takes a total of 16 A inputs and 4 B inputs (representing bits from 1 to 8), using only two-input NAND gates, and using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

• NOT: 1
• AND: 2
• OR: 3
• XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

• r3mainer: So any answer that uses no NAND gates at all will win? That should be easy. Am I allowed to use AND gates with 16 inputs?
• Rainbolt: @squeamishossifrage Did you read the question? AND gates add 2 to your score.
• Timtech: @squeamishossifrage One AND == two NAND
• Peter Taylor: @squeamishossifrage, "using only NAND gates". The scores for other gates are the minimum number of NAND gates required to build them; essentially it's defining some convenience macros.
• Rainbolt: @user80551 You need 16 bits to tell if 16 bits are ON or OFF. You need 4 bits to represent a 4 bit number. The number of ON bits must be greater than the 4 bit number. I don't really understand why that is so difficult. See the part of the question that says "total number of A inputs that are on is greater than the number represented by the B inputs."?

Answer 1

169 nands

Adds up the A's to get A{1,2,4,8,16}. Then does a binary comparison with the Bs.

I use a few more building blocks:

• FA = full adder, 9 nands (from here)
• HA = half adder, 7 nands (same ref)
• EQ = equality, 5 gates (a.k.a. xnor)

The half and full adders have 2 outputs - they are distinguished with an r for result and c for carry.

The A{1,2,4,8,16} are the outputs from the half adders.

enter image description here

• Justin: Wow. Just wow. Note that a half adder can be made in just 5 gates:codegolf.stackexchange.com/a/10848/9498 , 4 for xor, and 1 to invert the first nand in the xor. So we get an xor and an and. Picture: i.sstatic.net/qCFxa.png
• Keith Randall: @Quincunx: thanks, the better half adder lowers the count to 161. I don't think we need a quartus diagram, but if you'd like to I can update the answer with it.

Answer 2

751 nand gates

module BitCountingComparator(A, B, O);
 input [15:0] A;
 input [3:0] B;
 output O;
 wire [15:1] is;
 assign is[1] = A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] | A[13] | A[14] | A[15];
 wire [14:0] and2;
 assign and2[0] = A[0] & A[1];
 assign and2[1] = A[1] & A[2];
 assign and2[2] = A[2] & A[3];
 assign and2[3] = A[3] & A[4];
 assign and2[4] = A[4] & A[5];
 assign and2[5] = A[5] & A[6];
 assign and2[6] = A[6] & A[7];
 assign and2[7] = A[7] & A[8];
 assign and2[8] = A[8] & A[9];
 assign and2[9] = A[9] & A[10];
 assign and2[10] = A[10] & A[11];
 assign and2[11] = A[11] & A[12];
 assign and2[12] = A[12] & A[13];
 assign and2[13] = A[13] & A[14];
 assign and2[14] = A[14] & A[15];
 wire [13:0] and3;
 assign and3[0] = and2[0] & A[2];
 assign and3[1] = and2[1] & A[3];
 assign and3[2] = and2[2] & A[4];
 assign and3[3] = and2[3] & A[5];
 assign and3[4] = and2[4] & A[6];
 assign and3[5] = and2[5] & A[7];
 assign and3[6] = and2[6] & A[8];
 assign and3[7] = and2[7] & A[9];
 assign and3[8] = and2[8] & A[10];
 assign and3[9] = and2[9] & A[11];
 assign and3[10] = and2[10] & A[12];
 assign and3[11] = and2[11] & A[13];
 assign and3[12] = and2[12] & A[14];
 assign and3[13] = and2[13] & A[15];
 wire [12:0] and4;
 assign and4[0] = and3[0] & A[3];
 assign and4[1] = and3[1] & A[4];
 assign and4[2] = and3[2] & A[5];
 assign and4[3] = and3[3] & A[6];
 assign and4[4] = and3[4] & A[7];
 assign and4[5] = and3[5] & A[8];
 assign and4[6] = and3[6] & A[9];
 assign and4[7] = and3[7] & A[10];
 assign and4[8] = and3[8] & A[11];
 assign and4[9] = and3[9] & A[12];
 assign and4[10] = and3[10] & A[13];
 assign and4[11] = and3[11] & A[14];
 assign and4[12] = and3[12] & A[15];
 wire [11:0] and5;
 assign and5[0] = and4[0] & A[4];
 assign and5[1] = and4[1] & A[5];
 assign and5[2] = and4[2] & A[6];
 assign and5[3] = and4[3] & A[7];
 assign and5[4] = and4[4] & A[8];
 assign and5[5] = and4[5] & A[9];
 assign and5[6] = and4[6] & A[10];
 assign and5[7] = and4[7] & A[11];
 assign and5[8] = and4[8] & A[12];
 assign and5[9] = and4[9] & A[13];
 assign and5[10] = and4[10] & A[14];
 assign and5[11] = and4[11] & A[15];
 wire [10:0] and6;
 assign and6[0] = and5[0] & A[5];
 assign and6[1] = and5[1] & A[6];
 assign and6[2] = and5[2] & A[7];
 assign and6[3] = and5[3] & A[8];
 assign and6[4] = and5[4] & A[9];
 assign and6[5] = and5[5] & A[10];
 assign and6[6] = and5[6] & A[11];
 assign and6[7] = and5[7] & A[12];
 assign and6[8] = and5[8] & A[13];
 assign and6[9] = and5[9] & A[14];
 assign and6[10] = and5[10] & A[15];
 wire [9:0] and7;
 assign and7[0] = and6[0] & A[6];
 assign and7[1] = and6[1] & A[7];
 assign and7[2] = and6[2] & A[8];
 assign and7[3] = and6[3] & A[9];
 assign and7[4] = and6[4] & A[10];
 assign and7[5] = and6[5] & A[11];
 assign and7[6] = and6[6] & A[12];
 assign and7[7] = and6[7] & A[13];
 assign and7[8] = and6[8] & A[14];
 assign and7[9] = and6[9] & A[15];
 wire [8:0] and8;
 assign and8[0] = and7[0] & A[7];
 assign and8[1] = and7[1] & A[8];
 assign and8[2] = and7[2] & A[9];
 assign and8[3] = and7[3] & A[10];
 assign and8[4] = and7[4] & A[11];
 assign and8[5] = and7[5] & A[12];
 assign and8[6] = and7[6] & A[13];
 assign and8[7] = and7[7] & A[14];
 assign and8[8] = and7[8] & A[15];
 wire [7:0] and9;
 assign and9[0] = and8[0] & A[8];
 assign and9[1] = and8[1] & A[9];
 assign and9[2] = and8[2] & A[10];
 assign and9[3] = and8[3] & A[11];
 assign and9[4] = and8[4] & A[12];
 assign and9[5] = and8[5] & A[13];
 assign and9[6] = and8[6] & A[14];
 assign and9[7] = and8[7] & A[15];
 wire [6:0] and10;
 assign and10[0] = and9[0] & A[9];
 assign and10[1] = and9[1] & A[10];
 assign and10[2] = and9[2] & A[11];
 assign and10[3] = and9[3] & A[12];
 assign and10[4] = and9[4] & A[13];
 assign and10[5] = and9[5] & A[14];
 assign and10[6] = and9[6] & A[15];
 wire [5:0] and11;
 assign and11[0] = and10[0] & A[10];
 assign and11[1] = and10[1] & A[11];
 assign and11[2] = and10[2] & A[12];
 assign and11[3] = and10[3] & A[13];
 assign and11[4] = and10[4] & A[14];
 assign and11[5] = and10[5] & A[15];
 wire [4:0] and12;
 assign and12[0] = and11[0] & A[11];
 assign and12[1] = and11[1] & A[12];
 assign and12[2] = and11[2] & A[13];
 assign and12[3] = and11[3] & A[14];
 assign and12[4] = and11[4] & A[15];
 wire [3:0] and13;
 assign and13[0] = and12[0] & A[12];
 assign and13[1] = and12[1] & A[13];
 assign and13[2] = and12[2] & A[14];
 assign and13[3] = and12[3] & A[15];
 wire [2:0] and14;
 assign and14[0] = and13[0] & A[13];
 assign and14[1] = and13[1] & A[14];
 assign and14[2] = and13[2] & A[15];
 wire [1:0] and15;
 assign and15[0] = and14[0] & A[14];
 assign and15[1] = and14[1] & A[15];
 wire and16;
 assign and16 = and15[0] & A[15];
 assign is[2] = and2[0] | and2[1] | and2[2] | and2[3] | and2[4] | and2[5] | and2[6] | and2[7] | and2[8] | and2[9] | and2[10] | and2[11] | and2[12] | and2[13] | and2[15];
 assign is[3] = and3[0] | and3[1] | and3[2] | and3[3] | and3[4] | and3[5] | and3[6] | and3[7] | and3[8] | and3[9] | and3[10] | and3[11] | and3[12] | and3[14];
 assign is[4] = and4[0] | and4[1] | and4[2] | and4[3] | and4[4] | and4[5] | and4[6] | and4[7] | and4[8] | and4[9] | and4[10] | and4[11] | and4[13];
 assign is[5] = and5[0] | and5[1] | and5[2] | and5[3] | and5[4] | and5[5] | and5[6] | and5[7] | and5[8] | and5[9] | and5[10] | and5[12];
 assign is[6] = and6[0] | and6[1] | and6[2] | and6[3] | and6[4] | and6[5] | and6[6] | and6[7] | and6[8] | and6[9] | and6[11];
 assign is[7] = and7[0] | and7[1] | and7[2] | and7[3] | and7[4] | and7[5] | and7[6] | and7[7] | and7[8] | and7[10];
 assign is[8] = and8[0] | and8[1] | and8[2] | and8[3] | and8[4] | and8[5] | and8[6] | and8[7] | and8[9];
 assign is[9] = and9[0] | and9[1] | and9[2] | and9[3] | and9[4] | and9[5] | and9[6] | and9[8];
 assign is[10] = and10[0] | and10[1] | and10[2] | and10[3] | and10[4] | and10[5] | and10[7];
 assign is[11] = and11[0] | and11[1] | and11[2] | and11[3] | and11[4] | and11[6];
 assign is[12] = and12[0] | and12[1] | and12[2] | and12[3] | and12[5];
 assign is[13] = and13[0] | and13[1] | and13[2] | and13[4];
 assign is[14] = and14[0] | and14[1] | and14[3];
 assign is[15] = and15[0] | and15[2];
 assign is[16] = and16;
 wire [15:1] eB;
 eB[1] = B[0];
 eB[2] = B[1];
 eB[3] = B[1] & B[0];
 eB[4] = B[2];
 eB[5] = B[2] & B[0];
 eB[6] = B[2] & B[1];
 eB[7] = eB[6] & B[0];
 eB[8] = B[3];
 eB[9] = B[3] & B[0];
 eB[10] = B[3] & B[1];
 eB[11] = eB[10] & B[0];
 eB[12] = B[3] & B[2];
 eB[13] = eB[12] & B[0];
 eB[14] = eB[12] & B[1];
 eB[15] = eB[14] & B[0];
 assign O = is[1] & ~is[2] & ~eB[1] |
 is[2] & ~is[3] & ~eB[2] |
 is[3] & ~is[4] & ~eB[3] |
 is[4] & ~is[5] & ~eB[4] |
 is[5] & ~is[6] & ~eB[5] |
 is[6] & ~is[7] & ~eB[6] |
 is[7] & ~is[8] & ~eB[7] |
 is[8] & ~is[9] & ~eB[8] |
 is[9] & ~is[10] & ~eB[9] |
 is[10] & ~is[11] & ~eB[10] |
 is[11] & ~is[12] & ~eB[11] |
 is[12] & ~is[13] & ~eB[12] |
 is[13] & ~is[14] & ~eB[13] |
 is[14] & ~is[15] & ~eB[14] |
 is[15] & ~eB[15];
endmodule

This is not fully golfed yet. I gave the answer in Verilog because this way, I was able to write a program to output each section. If it is mandatory to answer with a diagram, please let me know. They are equivalent. & is and, ~ is not, and | is or.

My strategy:

• take A and put move all the 1s to the low numbers, store in is. (this is the majority of the program)
• take B and unpack it into 16 bits (I called it eB for expanded B)
• do a simple check.