Position of least significant bit that is set

by

Bit Twiddling Hacks offers an excellent collection of, er, bit twiddling hacks, with performance/optimisation discussion attached. My favourite solution for your problem (from that site) is «multiply and lookup»:

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Helpful references:

More Related Contents:

  1. Branchless code that maps zero, negative, and positive to 0, 1, 2
  2. Fastest way to produce a mask with n ones starting at position i
  3. Determine if int is not 0 with no if statements
  4. Invalid solution for code challenge with operator restrictions
  5. What are copy elision and return value optimization?
  6. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  7. Meaning of acronym SSO in the context of std::string
  8. Modular arithmetics and NTT (finite field DFT) optimizations
  9. What are the mechanics of short string optimization in libc++?
  10. gcc optimization flag -O3 makes code slower than -O2
  11. How to create a byte out of 8 bool values (and vice versa)?
  12. Constants and compiler optimization in C++
  13. Fastest way to get IPv4 address from string
  14. while (1) Vs. for (;;) Is there a speed difference?
  15. Should I use #define, enum or const?
  16. GCC C++ “Hello World” program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?
  17. C/C++: Optimization of pointers to string constants
  18. Why does Clang optimize away x * 1.0 but NOT x + 0.0?
  19. When do compilers inline C++ code?
  20. Fastest implementation of sine, cosine and square root in C++ (doesn’t need to be much accurate)
  21. Should I unify two similar kernels with an ‘if’ statement, risking performance loss?
  22. Efficient bitwise operations for counting bits or find the right|left most ones
  23. Get sum of values stored in __m256d with SSE/AVX
  24. how to optimize matrix multiplication (matmul) code to run fast on a single processor core
  25. Is a logical right shift by a power of 2 faster in AVR?
  26. Can I hint the optimizer by giving the range of an integer?
  27. Is it legal for a C++ optimizer to reorder calls to clock()?
  28. Is Visual Studio 2013 optimizing correctly in the presence of /OPT:ICF?
  29. How to reduce the size of executable produced by MinGW g++ compiler?
  30. std::array with aggregate initialization on g++ generates huge code

Leave a Comment