n & ~(n - 1) What does this function do?

Question

I was asked this and am printing out tables trying to find patterns but still don't see any meaning.

uint16_t hmmm(uint16_t n) {
  return (n & ~(n - 1));
}

Part of a digital filter? A double-helix animation if printed out?

I'm really wondering whether the person asking meant n & (n - 1): n & (n-1) what does this expression do?

Here's some output from a little test I wrote:

in: 0, 0b00000000   out: 0, 0b00000000
in: 1, 0b00000001   out: 1, 0b00000001
in: 2, 0b00000010   out: 2, 0b00000010
in: 3, 0b00000011   out: 1, 0b00000001
in: 4, 0b00000100   out: 4, 0b00000100
in: 5, 0b00000101   out: 1, 0b00000001
in: 6, 0b00000110   out: 2, 0b00000010
in: 7, 0b00000111   out: 1, 0b00000001
in: 8, 0b00001000   out: 8, 0b00001000
in: 9, 0b00001001   out: 1, 0b00000001
in: 10, 0b00001010  out: 2, 0b00000010
in: 11, 0b00001011  out: 1, 0b00000001
in: 12, 0b00001100  out: 4, 0b00000100
in: 13, 0b00001101  out: 1, 0b00000001
in: 14, 0b00001110  out: 2, 0b00000010
in: 15, 0b00001111  out: 1, 0b00000001
in: 16, 0b00010000  out: 16, 0b00010000
in: 17, 0b00010001  out: 1, 0b00000001
in: 18, 0b00010010  out: 2, 0b00000010
in: 19, 0b00010011  out: 1, 0b00000001
in: 20, 0b00010100  out: 4, 0b00000100
in: 21, 0b00010101  out: 1, 0b00000001
in: 22, 0b00010110  out: 2, 0b00000010
in: 23, 0b00010111  out: 1, 0b00000001
in: 24, 0b00011000  out: 8, 0b00001000
in: 25, 0b00011001  out: 1, 0b00000001
in: 26, 0b00011010  out: 2, 0b00000010
in: 27, 0b00011011  out: 1, 0b00000001
in: 28, 0b00011100  out: 4, 0b00000100
in: 29, 0b00011101  out: 1, 0b00000001
in: 30, 0b00011110  out: 2, 0b00000010
in: 31, 0b00011111  out: 1, 0b00000001
in: 32, 0b00100000  out: 32, 0b00100000
in: 33, 0b00100001  out: 1, 0b00000001
in: 34, 0b00100010  out: 2, 0b00000010
in: 35, 0b00100011  out: 1, 0b00000001
in: 36, 0b00100100  out: 4, 0b00000100
in: 37, 0b00100101  out: 1, 0b00000001
in: 38, 0b00100110  out: 2, 0b00000010
in: 39, 0b00100111  out: 1, 0b00000001
in: 40, 0b00101000  out: 8, 0b00001000
in: 41, 0b00101001  out: 1, 0b00000001
in: 42, 0b00101010  out: 2, 0b00000010
in: 43, 0b00101011  out: 1, 0b00000001
in: 44, 0b00101100  out: 4, 0b00000100
in: 45, 0b00101101  out: 1, 0b00000001
in: 46, 0b00101110  out: 2, 0b00000010
in: 47, 0b00101111  out: 1, 0b00000001
in: 48, 0b00110000  out: 16, 0b00010000
in: 49, 0b00110001  out: 1, 0b00000001
in: 50, 0b00110010  out: 2, 0b00000010
in: 51, 0b00110011  out: 1, 0b00000001
in: 52, 0b00110100  out: 4, 0b00000100
in: 53, 0b00110101  out: 1, 0b00000001
in: 54, 0b00110110  out: 2, 0b00000010
in: 55, 0b00110111  out: 1, 0b00000001
in: 56, 0b00111000  out: 8, 0b00001000
in: 57, 0b00111001  out: 1, 0b00000001
in: 58, 0b00111010  out: 2, 0b00000010
in: 59, 0b00111011  out: 1, 0b00000001
in: 60, 0b00111100  out: 4, 0b00000100
in: 61, 0b00111101  out: 1, 0b00000001
in: 62, 0b00111110  out: 2, 0b00000010
in: 63, 0b00111111  out: 1, 0b00000001
in: 64, 0b01000000  out: 64, 0b01000000
in: 65, 0b01000001  out: 1, 0b00000001
in: 66, 0b01000010  out: 2, 0b00000010
in: 67, 0b01000011  out: 1, 0b00000001
in: 68, 0b01000100  out: 4, 0b00000100
in: 69, 0b01000101  out: 1, 0b00000001
in: 70, 0b01000110  out: 2, 0b00000010
in: 71, 0b01000111  out: 1, 0b00000001
in: 72, 0b01001000  out: 8, 0b00001000
in: 73, 0b01001001  out: 1, 0b00000001
in: 74, 0b01001010  out: 2, 0b00000010
in: 75, 0b01001011  out: 1, 0b00000001
in: 76, 0b01001100  out: 4, 0b00000100
in: 77, 0b01001101  out: 1, 0b00000001
in: 78, 0b01001110  out: 2, 0b00000010
in: 79, 0b01001111  out: 1, 0b00000001
in: 80, 0b01010000  out: 16, 0b00010000
in: 81, 0b01010001  out: 1, 0b00000001
in: 82, 0b01010010  out: 2, 0b00000010
in: 83, 0b01010011  out: 1, 0b00000001
in: 84, 0b01010100  out: 4, 0b00000100
in: 85, 0b01010101  out: 1, 0b00000001
in: 86, 0b01010110  out: 2, 0b00000010
in: 87, 0b01010111  out: 1, 0b00000001
in: 88, 0b01011000  out: 8, 0b00001000
in: 89, 0b01011001  out: 1, 0b00000001
in: 90, 0b01011010  out: 2, 0b00000010
in: 91, 0b01011011  out: 1, 0b00000001
in: 92, 0b01011100  out: 4, 0b00000100
in: 93, 0b01011101  out: 1, 0b00000001
in: 94, 0b01011110  out: 2, 0b00000010
in: 95, 0b01011111  out: 1, 0b00000001
in: 96, 0b01100000  out: 32, 0b00100000
in: 97, 0b01100001  out: 1, 0b00000001
in: 98, 0b01100010  out: 2, 0b00000010
in: 99, 0b01100011  out: 1, 0b00000001
in: 100, 0b01100100 out: 4, 0b00000100
in: 101, 0b01100101 out: 1, 0b00000001
in: 102, 0b01100110 out: 2, 0b00000010
in: 103, 0b01100111 out: 1, 0b00000001
in: 104, 0b01101000 out: 8, 0b00001000
in: 105, 0b01101001 out: 1, 0b00000001
in: 106, 0b01101010 out: 2, 0b00000010
in: 107, 0b01101011 out: 1, 0b00000001
in: 108, 0b01101100 out: 4, 0b00000100
in: 109, 0b01101101 out: 1, 0b00000001
in: 110, 0b01101110 out: 2, 0b00000010
in: 111, 0b01101111 out: 1, 0b00000001
in: 112, 0b01110000 out: 16, 0b00010000
in: 113, 0b01110001 out: 1, 0b00000001
in: 114, 0b01110010 out: 2, 0b00000010
in: 115, 0b01110011 out: 1, 0b00000001
in: 116, 0b01110100 out: 4, 0b00000100
in: 117, 0b01110101 out: 1, 0b00000001
in: 118, 0b01110110 out: 2, 0b00000010
in: 119, 0b01110111 out: 1, 0b00000001
in: 120, 0b01111000 out: 8, 0b00001000
in: 121, 0b01111001 out: 1, 0b00000001
in: 122, 0b01111010 out: 2, 0b00000010
in: 123, 0b01111011 out: 1, 0b00000001
in: 124, 0b01111100 out: 4, 0b00000100
in: 125, 0b01111101 out: 1, 0b00000001
in: 126, 0b01111110 out: 2, 0b00000010
in: 127, 0b01111111 out: 1, 0b00000001
in: 128, 0b10000000 out: 128, 0b10000000
in: 129, 0b10000001 out: 1, 0b00000001
in: 130, 0b10000010 out: 2, 0b00000010
in: 131, 0b10000011 out: 1, 0b00000001
in: 132, 0b10000100 out: 4, 0b00000100
in: 133, 0b10000101 out: 1, 0b00000001
in: 134, 0b10000110 out: 2, 0b00000010
in: 135, 0b10000111 out: 1, 0b00000001
in: 136, 0b10001000 out: 8, 0b00001000
in: 137, 0b10001001 out: 1, 0b00000001
in: 138, 0b10001010 out: 2, 0b00000010
in: 139, 0b10001011 out: 1, 0b00000001
in: 140, 0b10001100 out: 4, 0b00000100
in: 141, 0b10001101 out: 1, 0b00000001
in: 142, 0b10001110 out: 2, 0b00000010
in: 143, 0b10001111 out: 1, 0b00000001
in: 144, 0b10010000 out: 16, 0b00010000
in: 145, 0b10010001 out: 1, 0b00000001
in: 146, 0b10010010 out: 2, 0b00000010
in: 147, 0b10010011 out: 1, 0b00000001
in: 148, 0b10010100 out: 4, 0b00000100
in: 149, 0b10010101 out: 1, 0b00000001
in: 150, 0b10010110 out: 2, 0b00000010
in: 151, 0b10010111 out: 1, 0b00000001
in: 152, 0b10011000 out: 8, 0b00001000
in: 153, 0b10011001 out: 1, 0b00000001
in: 154, 0b10011010 out: 2, 0b00000010
in: 155, 0b10011011 out: 1, 0b00000001
in: 156, 0b10011100 out: 4, 0b00000100
in: 157, 0b10011101 out: 1, 0b00000001
in: 158, 0b10011110 out: 2, 0b00000010
in: 159, 0b10011111 out: 1, 0b00000001
in: 160, 0b10100000 out: 32, 0b00100000
in: 161, 0b10100001 out: 1, 0b00000001
in: 162, 0b10100010 out: 2, 0b00000010
in: 163, 0b10100011 out: 1, 0b00000001
in: 164, 0b10100100 out: 4, 0b00000100
in: 165, 0b10100101 out: 1, 0b00000001
in: 166, 0b10100110 out: 2, 0b00000010
in: 167, 0b10100111 out: 1, 0b00000001
in: 168, 0b10101000 out: 8, 0b00001000
in: 169, 0b10101001 out: 1, 0b00000001
in: 170, 0b10101010 out: 2, 0b00000010
in: 171, 0b10101011 out: 1, 0b00000001
in: 172, 0b10101100 out: 4, 0b00000100
in: 173, 0b10101101 out: 1, 0b00000001
in: 174, 0b10101110 out: 2, 0b00000010
in: 175, 0b10101111 out: 1, 0b00000001
in: 176, 0b10110000 out: 16, 0b00010000
in: 177, 0b10110001 out: 1, 0b00000001
in: 178, 0b10110010 out: 2, 0b00000010
in: 179, 0b10110011 out: 1, 0b00000001
in: 180, 0b10110100 out: 4, 0b00000100
in: 181, 0b10110101 out: 1, 0b00000001
in: 182, 0b10110110 out: 2, 0b00000010
in: 183, 0b10110111 out: 1, 0b00000001
in: 184, 0b10111000 out: 8, 0b00001000
in: 185, 0b10111001 out: 1, 0b00000001
in: 186, 0b10111010 out: 2, 0b00000010
in: 187, 0b10111011 out: 1, 0b00000001
in: 188, 0b10111100 out: 4, 0b00000100
in: 189, 0b10111101 out: 1, 0b00000001
in: 190, 0b10111110 out: 2, 0b00000010
in: 191, 0b10111111 out: 1, 0b00000001
in: 192, 0b11000000 out: 64, 0b01000000
in: 193, 0b11000001 out: 1, 0b00000001
in: 194, 0b11000010 out: 2, 0b00000010
in: 195, 0b11000011 out: 1, 0b00000001
in: 196, 0b11000100 out: 4, 0b00000100
in: 197, 0b11000101 out: 1, 0b00000001
in: 198, 0b11000110 out: 2, 0b00000010
in: 199, 0b11000111 out: 1, 0b00000001
in: 200, 0b11001000 out: 8, 0b00001000
in: 201, 0b11001001 out: 1, 0b00000001
in: 202, 0b11001010 out: 2, 0b00000010
in: 203, 0b11001011 out: 1, 0b00000001
in: 204, 0b11001100 out: 4, 0b00000100
in: 205, 0b11001101 out: 1, 0b00000001
in: 206, 0b11001110 out: 2, 0b00000010
in: 207, 0b11001111 out: 1, 0b00000001
in: 208, 0b11010000 out: 16, 0b00010000
in: 209, 0b11010001 out: 1, 0b00000001
in: 210, 0b11010010 out: 2, 0b00000010
in: 211, 0b11010011 out: 1, 0b00000001
in: 212, 0b11010100 out: 4, 0b00000100
in: 213, 0b11010101 out: 1, 0b00000001
in: 214, 0b11010110 out: 2, 0b00000010
in: 215, 0b11010111 out: 1, 0b00000001
in: 216, 0b11011000 out: 8, 0b00001000
in: 217, 0b11011001 out: 1, 0b00000001
in: 218, 0b11011010 out: 2, 0b00000010
in: 219, 0b11011011 out: 1, 0b00000001
in: 220, 0b11011100 out: 4, 0b00000100
in: 221, 0b11011101 out: 1, 0b00000001
in: 222, 0b11011110 out: 2, 0b00000010
in: 223, 0b11011111 out: 1, 0b00000001
in: 224, 0b11100000 out: 32, 0b00100000
in: 225, 0b11100001 out: 1, 0b00000001
in: 226, 0b11100010 out: 2, 0b00000010
in: 227, 0b11100011 out: 1, 0b00000001
in: 228, 0b11100100 out: 4, 0b00000100
in: 229, 0b11100101 out: 1, 0b00000001
in: 230, 0b11100110 out: 2, 0b00000010
in: 231, 0b11100111 out: 1, 0b00000001
in: 232, 0b11101000 out: 8, 0b00001000
in: 233, 0b11101001 out: 1, 0b00000001
in: 234, 0b11101010 out: 2, 0b00000010
in: 235, 0b11101011 out: 1, 0b00000001
in: 236, 0b11101100 out: 4, 0b00000100
in: 237, 0b11101101 out: 1, 0b00000001
in: 238, 0b11101110 out: 2, 0b00000010
in: 239, 0b11101111 out: 1, 0b00000001
in: 240, 0b11110000 out: 16, 0b00010000
in: 241, 0b11110001 out: 1, 0b00000001
in: 242, 0b11110010 out: 2, 0b00000010
in: 243, 0b11110011 out: 1, 0b00000001
in: 244, 0b11110100 out: 4, 0b00000100
in: 245, 0b11110101 out: 1, 0b00000001
in: 246, 0b11110110 out: 2, 0b00000010
in: 247, 0b11110111 out: 1, 0b00000001
in: 248, 0b11111000 out: 8, 0b00001000
in: 249, 0b11111001 out: 1, 0b00000001
in: 250, 0b11111010 out: 2, 0b00000010
in: 251, 0b11111011 out: 1, 0b00000001
in: 252, 0b11111100 out: 4, 0b00000100
in: 253, 0b11111101 out: 1, 0b00000001
in: 254, 0b11111110 out: 2, 0b00000010

Answer 1

I believe it clears every bit except the first turned on bit..

Assume

n = ?????????10000

a set of bits then 1 then some amount of zeros..

n-1 will look like this

n-1 = ?????????01111

~(n-1) = ~?~?~?~?~?~?~?~?~?10000

then the and operator leaves just the first part

n = ?????????10000 &     ~(n-1) = ~?~?~?~?~?~?~?~?~?10000
  result 00000010000

Specifically for odd numbers it is always 1 cause the first turned on bit it the first one. If n was a power of 2 then obviously it will remain unchanged

Answer 2

This function takes an integer, and returns the longest suffix of this integer which is a power of 2.

Answer 3

It seems to me to be finding the rightmost 1 in the bitstring.

Look at the 2 following cases:

• The number is odd. In that case (n-1) is the same number without the last bit set. Invert that and you get a mask with 0's where the original has 1's except the last spot.

Example: n = 01101, (n-1) = 01100, ~(n-1) = 10011, n & ~(n-1) = 01101 & 10011 = 00001

• The number is even. Then the same thing applies as case 1, except, all bits to the right of the last 1 are 0 during the AND operation.

Example: n = 01100, (n-1) = 01011, ~(n-1) = 10100, n & ~(n-1) = 01100 & 10100 = 00100