3 ms·
probably 'a properly implemented one' would be using combinational logic that can calculate popcnt in a single cycle, or maybe a two-cycle pipelined implementat
by kragen 2y ago
probably 'a properly implemented one' would be using combinational logic that can calculate popcnt in a single cycle, or maybe a two-cycle pipelined implementation, which is not the same thing as a microcoded popcnt
here's a simple combinational 8-bit popcnt circuit i just simulated, just using ripple carry. unfortunately i think falstad's circuit.js doesn't have a way to simulate propagation delays; i think the point where you start wanting lookahead carry instead of ripple carry is when you're doing a 16-bit popcnt, because a 64-bit ripple-carry popcnt would have three more full adders of propagation delay over this one
https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgxjCRCaQvwKPP25pK4NgBkQLDNzDcmaYQqhqAZgEMANgGcG1SFJlg5tYUvzm1ELXoNIj02fMJVLKtzZB39h4y6CFspB3r4OUBzESIGqLGAo4NxGnDGm8kImCaEp0TLYiaoFSZEA7jJ4VHHFqkblTJUi+YkCdc1NTMU0wm0NVAJ9OWz1jQpUvElUvY3dMhOzvfMWEwk9w3N8qzybmW1L201GALIguJvcCNm1ICjQCGwnNHAHl4kTVLf3jwJbrzk3d3WE0wbz4BSm6yYE2wCFBp1hZQ2NwwiShYIR0w+KKRIMRg2weD40MJeMa4IqVBhiV6xXJnUSuMxpzQ7XJTJQT3aHIhqS5nOK3MivMCVKyiVFuTSZkF8QZnKcJjMoo88Op4B8Oj8jgC6VOJJVBL4VQ19n8zl1uJVjPV4TNitEnKt8ptmoiuW40JZW3JYiqUSQIVUuNq60DHvOiJCsxCgraMc5wPlUW4ZwO2EIwmBkHE7HKqZ+Xla61T3sgYJZbVT5LGzJ5AieVUyNBWmV9EnKNZrDcmiNTs1T73W3c4iW7hsRY5JNfHx1oP2IiT+I7UnzYQA https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB...
if you have a lot of popcnts to do, you can productively bitslice them so they're fast even without hardware support