n & (n-1) what does this expression do? [duplicate]

by

It’s figuring out if n is either 0 or an exact power of two.

It works because a binary power of two is of the form 1000...000 and subtracting one will give you 111...111. Then, when you AND those together, you get zero, such as with:

  1000 0000 0000 0000
&  111 1111 1111 1111
  ==== ==== ==== ====
= 0000 0000 0000 0000

Any non-power-of-two input value (other than zero) will not give you zero when you perform that operation.

For example, let’s try all the 4-bit combinations:

     <----- binary ---->
 n      n    n-1   n&(n-1)
--   ----   ----   -------
 0   0000   0111    0000 *
 1   0001   0000    0000 *
 2   0010   0001    0000 *
 3   0011   0010    0010
 4   0100   0011    0000 *
 5   0101   0100    0100
 6   0110   0101    0100
 7   0111   0110    0110
 8   1000   0111    0000 *
 9   1001   1000    1000
10   1010   1001    1000
11   1011   1010    1010
12   1100   1011    1000
13   1101   1100    1100
14   1110   1101    1100
15   1111   1110    1110

You can see that only 0 and the powers of two (1, 2, 4 and 8) result in a 0000/false bit pattern, all others are non-zero or true.

More Related Contents:

  1. Seriously What's wrong in my code
  2. Why do I get a segmentation fault when writing to a “char *s” initialized with a string literal, but not “char s[]”?
  3. Specifically, what’s dangerous about casting the result of malloc?
  4. The program doesn’t stop on scanf(“%c”, &ch) line, why? [duplicate]
  5. Are the shift operators () arithmetic or logical in C?
  6. Printing leading 0’s in C
  7. Function declaration: K&R vs ANSI [duplicate]
  8. Is char guaranteed to be exactly 8-bit long? [duplicate]
  9. Is malloc thread-safe?
  10. How to define a typedef struct containing pointers to itself?
  11. Unsized array declaration in a struct
  12. Why is “while( !feof(file) )” always wrong?
  13. Does guarding a variable with a pthread mutex guarantee it’s also not cached?
  14. Fastest way to clamp a real (fixed/floating point) value?
  15. Simpler way of sorting three numbers
  16. How do I gaussian blur an image without using any in-built gaussian functions?
  17. Kernel zeroes memory?
  18. C function with no parameters behavior
  19. Uniformity of random numbers taken modulo N
  20. Beep on Linux in C
  21. C Macros to create strings
  22. Why does a=(b++) have the same behavior as a=b++?
  23. Why can’t I assign values to global variables outside a function in C?
  24. Wrong format specifiers in scanf (or) printf
  25. How to use nanosleep() in C? What are `tim.tv_sec` and `tim.tv_nsec`?
  26. Associative arrays in C
  27. Should we use exit() in C?
  28. Default case in a switch condition
  29. C: SIGALRM – alarm to display message every second
  30. Getting multiple values with scanf()

Leave a Comment