meaning of (number) & (-number)

by

Assuming 2’s complement (or that i is unsigned), -i is equal to ~i+1.

i & (~i + 1) is a trick to extract the lowest set bit of i.

It works because what +1 actually does is to set the lowest clear bit, and clear all bits lower than that. So the only bit that is set in both i and ~i+1 is the lowest set bit from i (that is, the lowest clear bit in ~i). The bits lower than that are clear in ~i+1, and the bits higher than that are non-equal between i and ~i.

Using it in a loop seems odd unless the loop body modifies i, because i = i & (-i) is an idempotent operation: doing it twice gives the same result again.

[Edit: in a comment elsewhere you point out that the code is actually i += i & (-i). So what that does for non-zero i is to clear the lowest group of set bits of i, and set the next clear bit above that, for example 101100 -> 110000. For i with no clear bit higher than the lowest set bit (including i = 0), it sets i to 0. So if it weren’t for the fact that i starts at 0, each loop would increase i by at least twice as much as the previous loop, sometimes more, until eventually it exceeds n and breaks or goes to 0 and loops forever.

It would normally be inexcusable to write code like this without a comment, but depending on the domain of the problem maybe this is an “obvious” sequence of values to loop over.]

More Related Contents:

  1. "imspossible" error on a simplest code [closed]
  2. Calling method on an object that is a private member of a class
  3. Capture characters from standard input without waiting for enter to be pressed
  4. How to redirect cin and cout to files?
  5. Is < faster than
  6. Type of integer literals not int by default?
  7. How does photoshop blend two images together? [closed]
  8. What are the pointer-to-member operators ->* and .* in C++?
  9. How do I check if a C++ string is an int?
  10. How to initialize std::vector from C-style array?
  11. fork() branches more than expected?
  12. Case insensitive std::string.find()
  13. inlining failed in call to always_inline ‘__m256d _mm256_broadcast_sd(const double*)’
  14. How to create a UTF-8 string literal in Visual C++ 2008
  15. “If constexpr” in C++17 does not work in a non-templated function
  16. How to end C++ code
  17. Rewinding std::cout to go back to the beginning of a line
  18. Multiple SFINAE class template specialisations using void_t
  19. Why void_t doesnt work in SFINAE but enable_if does
  20. Can raw pointers be used instead of iterators with STL algorithms for containers with linear storage?
  21. Get home directory in Linux
  22. friend AND inline method, what’s the point ?
  23. MinGW / CxxTest bizarre errors
  24. std::back_inserter for a std::set?
  25. How to create std::array with initialization list without providing size directly [duplicate]
  26. Should the Copy-and-Swap Idiom become the Copy-and-Move Idiom in C++11?
  27. How do I call a pointer-to-member-function?
  28. What’s the advantage of using std::allocator instead of new in C++?
  29. version `CXXABI_1.3.8′ not found (required by …) [duplicate]
  30. How to count clock cycles with RDTSC in GCC x86? [duplicate]

Leave a Comment