How to get position of right most set bit in C

by

This answer Unset the rightmost set bit tells both how to get and unset rightmost set bit for an unsigned integer or signed integer represented as two’s complement.

get rightmost set bit, 

x & -x
// or
x & (~x + 1)

unset rightmost set bit,

x &= x - 1
// or
x -= x & -x  // rhs is rightmost set bit

why it works

x:                     leading bits  1  all 0
~x:           reversed leading bits  0  all 1
~x + 1 or -x: reversed leading bits  1  all 0
x & -x:                       all 0  1  all 0

eg, let x = 112, and choose 8-bit for simplicity, though the idea is same for all size of integer.

// example for get rightmost set bit
x:             01110000
~x:            10001111
-x or ~x + 1:  10010000
x & -x:        00010000

// example for unset rightmost set bit
x:             01110000
x-1:           01101111
x & (x-1):     01100000

More Related Contents:

  1. Bit manipulation, return 0 if x != 0, or nonzero otherwise
  2. What is Bit Masking?
  3. Are the results of bitwise operations on signed integers defined?
  4. Operator precedence (bitwise ‘&’ lower than ‘==’)
  5. Getting each individual digit from a whole integer
  6. Casting float to int (bitwise) in C
  7. What does the statement if (counter & (1
  8. Bitwise ‘&’ operator
  9. Encoding int value as an IEEE-754 float (binary32)
  10. Why use the Bitwise-Shift operator for values in a C enum definition?
  11. Decimal to Binary
  12. Can you control what a bitwise right shift will fill in C?
  13. What is bit masking?
  14. Competitive programming: "Time exceeded error"
  15. Why doesn’t ++ increment integer value?
  16. Using GCC to produce readable assembly?
  17. C dynamically growing array
  18. Are negative array indexes allowed in C?
  19. When was the NULL macro not 0?
  20. Is it safe to read past the end of a buffer within the same page on x86 and x64?
  21. How to pass an array of Swift strings to a C function taking a char ** parameter
  22. How to implement getch() function of C in Linux?
  23. C – split string into an array of strings
  24. How to find the socket connection state in C?
  25. Kernel zeroes memory?
  26. C function with no parameters behavior
  27. Wrong format specifiers in scanf (or) printf
  28. Why does forking my process cause the file to be read infinitely
  29. Code for malloc and free
  30. ftell at a position past 2GB

Leave a Comment