From 449e7a410bdaee17e139c8121cdf125d82a73dff Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 6 Aug 2020 16:15:55 -0700 Subject: Fix CountLeadingZeroes on MSVC (#3028) We just had the logic there wrong - MSVC's intrinsic returns the bit index, not the number of leading zeros. That's identical when scanning forward but not in reverse... Fixes #2942 --- src/support/bits.cpp | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'src/support/bits.cpp') diff --git a/src/support/bits.cpp b/src/support/bits.cpp index 63b744eb4..992b97955 100644 --- a/src/support/bits.cpp +++ b/src/support/bits.cpp @@ -116,7 +116,10 @@ template<> int CountLeadingZeroes(uint32_t v) { #elif defined(_MSC_VER) unsigned long count; _BitScanReverse(&count, v); - return (int)count; + // BitScanReverse gives the bit position (0 for the LSB, then 1, etc.) of the + // first bit that is 1, when looking from the MSB. To count leading zeros, we + // need to adjust that. + return 31 - int(count); #else // See Stanford bithacks, find the log base 2 of an N-bit integer in // O(lg(N)) operations with multiply and lookup: @@ -142,7 +145,7 @@ template<> int CountLeadingZeroes(uint64_t v) { #elif defined(_MSC_VER) && defined(_M_X64) unsigned long count; _BitScanReverse64(&count, v); - return (int)count; + return 63 - int(count); #else return v >> 32 ? CountLeadingZeroes((uint32_t)(v >> 32)) : 32 + CountLeadingZeroes((uint32_t)v); -- cgit v1.2.3