Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]

by

Any unsigned integer ‘n’ will have the following last k digits: One followed by (k-1) zeroes: 100…0
Note that k can be 1 in which case there are no zeroes.

(n – 1) will end in this format: Zero followed by (k-1) 1’s: 011…1

n & (n-1) will therefore end in ‘k’ zeroes: 100…0 & 011…1 = 000…0

Hence n & (n – 1) will eliminate the rightmost ‘1’. Each iteration of this will basically remove the rightmost ‘1’ digit and hence you can count the number of 1’s.

More Related Contents:

  1. Mixing two arrays by alternating elements two by two
  2. banker’s algorithm in c++
  3. What is the difference between palindrome permutation and permutation? [closed]
  4. How to replace all occurrences of a character in string?
  5. Rotating a point about another point (2D)
  6. Sorting zipped (locked) containers in C++ using boost or the STL
  7. Create Random Number Sequence with No Repeats
  8. std::transform() and toupper(), no matching function
  9. C++ string::find complexity
  10. C++ Efficiently Calculating a Running Median [duplicate]
  11. Special simple random number generator
  12. Finding nearest point in an efficient way
  13. Fast n choose k mod p for large n?
  14. TMP: how to generalize a Cartesian Product of Vectors?
  15. How can std::make_heap be implemented while making at most 3N comparisons?
  16. Writing a simple equation parser
  17. What is the right approach when using STL container for median calculation?
  18. Howto create combinations of several vectors without hardcoding loops in C++?
  19. Inverting a 4×4 matrix
  20. Print 2-D Array in clockwise expanding spiral from center
  21. std::back_inserter for a std::set?
  22. How to rotate a N x N matrix by 90 degrees? [closed]
  23. Ways to do modulo multiplication with primitive types
  24. Removing ‘#include ‘ doesn’t break the code
  25. Why there is no std::copy_if algorithm?
  26. LRU implementation in production code
  27. Is it possible to implement lock free map in C++
  28. priority queue with limited space: looking for a good algorithm
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment