What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?

by

GCC has:

 -- Built-in Function: int __builtin_clz (unsigned int x)
     Returns the number of leading 0-bits in X, starting at the most
     significant bit position.  If X is 0, the result is undefined.

 -- Built-in Function: int __builtin_clzl (unsigned long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long'.

 -- Built-in Function: int __builtin_clzll (unsigned long long)
     Similar to `__builtin_clz', except the argument type is `unsigned
     long long'.

I’d expect them to be translated into something reasonably efficient for your current platform, whether it be one of those fancy bit-twiddling algorithms, or a single instruction.

A useful trick if your input can be zero is __builtin_clz(x | 1): unconditionally setting the low bit without modifying any others makes the output 31 for x=0, without changing the output for any other input.

To avoid needing to do that, your other option is platform-specific intrinsics like ARM GCC’s __clz (no header needed), or x86’s _lzcnt_u32 on CPUs that support the lzcnt instruction. (Beware that lzcnt decodes as bsr on older CPUs instead of faulting, which gives 31-lzcnt for non-zero inputs.)

There’s unfortunately no way to portably take advantage of the various CLZ instructions on non-x86 platforms that do define the result for input=0 as 32 or 64 (according to the operand width). x86’s lzcnt does that, too, while bsr produces a bit-index that the compiler has to flip unless you use 31-__builtin_clz(x).

(The “undefined result” is not C Undefined Behavior, just a value that isn’t defined. It’s actually whatever was in the destination register when the instruction ran. AMD documents this, Intel doesn’t, but Intel’s CPUs do implement that behaviour. But it’s not whatever was previously in the C variable you’re assigning to, that’s not usually how things work when gcc turns C into asm. See also Why does breaking the “output dependency” of LZCNT matter?)

More Related Contents:

  1. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  2. Rounding up to next power of 2
  3. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  4. Compute fast log base 2 ceiling
  5. Algorithm to generate bit mask
  6. Algorithm to find the smallest number in an array in C [closed]
  7. Finding target sum of two numbers in array
  8. How to remove blank spaces from buffer [closed]
  9. Improve INSERT-per-second performance of SQLite
  10. Position of least significant bit that is set
  11. Algorithm: efficient way to remove duplicate integers from an array
  12. how to rasterize rotated rectangle (in 2d by setpixel)
  13. Project Euler Question 14 (Collatz Problem)
  14. What’s bad about shifting a 32-bit variable 32 bits?
  15. How do you print the EXACT value of a floating point number?
  16. How to add two numbers without using ++ or + or another arithmetic operator
  17. Time complexity of a recursive algorithm
  18. Print all the permutations of a string in C
  19. Given an audio stream, find when a door slams (sound pressure level calculation?)
  20. Linked list recursive reverse
  21. warning: left shift count >= width of type
  22. Generating a uniform distribution of INTEGERS in C
  23. Are constant C expressions evaluated at compile time or at runtime?
  24. Finding out the duplicate element in an array
  25. How to replace bits in a bitfield without affecting other bits using C
  26. Faster approach to checking for an all-zero buffer in C?
  27. Does C have any tools for doing string addition?
  28. C Programming – XOR Bitwise Operation
  29. Variable Sized Arrays vs calloc in C
  30. A possible algorithm for determining whether two strings are anagrams of one another? [closed]

Leave a Comment