From be4321913611510b23648226d6cbe0f1419d02c4 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sun, 25 Jan 2009 18:00:57 +0100 Subject: [PATCH] Rever count_1s() optimizations They are wrong for all ones case. Signed-off-by: Marco Costalba --- src/bitboard.h | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/src/bitboard.h b/src/bitboard.h index 2280f66c..1aefd8ad 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -395,21 +395,23 @@ inline int count_1s_max_15(Bitboard b) { inline int count_1s(Bitboard b) { unsigned w = unsigned(b >> 32), v = unsigned(b); - v -= (v >> 1) & 0x55555555; + v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits w -= (w >> 1) & 0x55555555; - v += w; - v = ((v >> 2) & 0x33333333) + (v & 0x33333333); - v = ((v >> 4) + v) & 0x0F0F0F0F; + v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits + w = ((w >> 2) & 0x33333333) + (w & 0x33333333); + v = ((v >> 4) + v) & 0x0F0F0F0F; // 0-8 in 8 bits + v += (((w >> 4) + w) & 0x0F0F0F0F); // 0-16 in 8 bits v *= 0x01010101; // mul is fast on amd procs return int(v >> 24); } inline int count_1s_max_15(Bitboard b) { unsigned w = unsigned(b >> 32), v = unsigned(b); - v -= (v >> 1) & 0x55555555; + v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits w -= (w >> 1) & 0x55555555; - v += w; - v = ((v >> 2) & 0x33333333) + (v & 0x33333333); + v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits + w = ((w >> 2) & 0x33333333) + (w & 0x33333333); + v += w; // 0-8 in 4 bits v *= 0x11111111; return int(v >> 28); } -- 2.39.2