How to count efficiently the number of trailing zeros in a binary representation of an integer number?
6 Answers
Here's a nice, quick and easy implementation:
public static int NumberOfTrailingZeros(int i)
{
return _lookup[(i & -i) % 37];
}
private static readonly int[] _lookup =
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18
};
(Taken from http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup.)
6 Comments
LukeH
@Downvoter: Would you care to explain why you think this answer deserves a downvote?
Jake 'Alquimista' LEE
I didn't downvote, but I can imagine very well why people are downvoting. That modulo part is costly. It will translate to a 64-bit long multiply in best case, or even a division that costs dozens of cycles in worst case. And it requires 37*4 bytes memory. To sum it up, it is hardly any better than the iterative version below if not worse. Considering most architectures feature the clz instruction since decades, your suggestion isn't a very helpful one.
LukeH
@Jake: I agree that this might not be optimal, but I did provide a link to the bithacks page which has some alternative methods. Besides, we're talking about C# here, a managed language: if you know of any way to force a CLZ/CTZ instruction from C# and/or .NET then please share it.
LukeH
@Jake: If the OP is happy to work within the constraints of the .NET runtime then a mod call and 147 bytes of storage are likely to be of little concern (and if they are a problem then the OP is free to benchmark the alternatives until they find one that meets their requirements).
Jake 'Alquimista' LEE
You were curious about why people downvoted. I gave you the answer. And here is the next one: codeproject.com/Articles/1392/…
|
Just make a mask starting at the first digit and keep moving it over until it finds something:
public static int numTrailingBinaryZeros(int n)
{
int mask = 1;
for (int i = 0; i < 32; i++, mask <<= 1)
if ((n & mask) != 0)
return i;
return 32;
}
Comments
Starting from .Net Core 3.0 there is BitOperations.TrailingZeroCount i dont know past versions but if i look into its current .net 7 source code it is inlined into Bmi1.TrailingZeroCount which is compiler intrinsic and converted to tzcnt x86 asm instruction on supported x86 environments. it has hardware accelerated implementation for ARM and falls back to software implementation as last resort.
1 Comment
gen.error
This should be the accepted answer now. Intrinsics make a lot of these nice bithacks very, very contraproductive today, be it in C# or Java. They probably didn't exist back when the questions was asked, but nowadays, everyone trying to create an optimized version without first profiling (or checking the generated code) just shoots themselves into the knee.
In java it is implemented like:
public static int numberOfTrailingZeros(int i) {
// HD, Figure 5-14
int y;
if (i == 0) return 32;
int n = 31;
y = i <<16; if (y != 0) { n = n -16; i = y; }
y = i << 8; if (y != 0) { n = n - 8; i = y; }
y = i << 4; if (y != 0) { n = n - 4; i = y; }
y = i << 2; if (y != 0) { n = n - 2; i = y; }
return n - ((i << 1) >>> 31);
}
I think idea is from "Hacker's Delight"
3 Comments
voxoid
An unrolled binary search loop -- brilliant! +1 for finding an existing, grossly tried-and-true method.
voxoid
The return line won't compile in C# because C# doesn't have the zero-fill right-shift operator >>> . Instead I believe it should be
return n - (int)((uint)(i << 1) >> 31);
thecodewarrior
Something of a necropost, but that's the implementation from the Java standard library (
Integer.numberOfTrailingZeros).int trailingZeros(int n) {
if(!n)
return 32;
for(int s = 0; !(n & 1); s++)
n >>= 1;
return s;
}
Comments
This variation on the Java version uses a bit more bit twiddling to remove the last conditional test:
public static uint Ctz(uint num)
{
if (num == 0) return 32; // optional, otherwise returns 0
uint tmp;
uint res = 0;
num &= (uint)-(int)num; // Isolate bit
tmp = num >> 16; if (tmp != 0) { num = tmp; res += 16; }
tmp = num >> 8; if (tmp != 0) { num = tmp; res += 8; }
tmp = num >> 4; if (tmp != 0) { num = tmp; res += 4; }
return res + ((num >> 1) - (num >> 3));
}
intorlong?