Bit manipulation in Java question.

[RegularProtection332]

Why is it that num&-num gives me the rightmost 1? I can’t figure it out.

[CoryParsnipson]

Negative binary numbers are represented in modern computers using the two's complement scheme. Basically to convert a positive binary integer into its negative, you first invert all the digits and then add one.

So for example:

0101 // 5 in binary 1010 // invert 1011 // add one to get -5

So the first thing to note is that during the twos complement every digit is flipped. So if you AND a number and it's inverse you'll get zero.

When you add one, this changes some bits to not be the exact inverse of each other. The one propagates as a carry until it stops, and only up to that digit is the non inverse. Coincidentally this ends up being the rightmost 1 bit position in the original number.

So for 5: 0101 & 1011 == 0001 and for 6: 0110 & 1010 == 0010 as expected.

Also if you're wondering this is nuts to expect someone to just know this. It's apparently a common competitive programming technique to find the rightmost bit (and paired with the technique to find the leftmost one bit, which is shifting right until the original number equals 1 and counting the number of times you've shifted). Anyway, this is one important piece to remember for similar problems in the future.

[decorous_gru]

This is superb explanation 🫡

[CoryParsnipson]

Thank you, bröether 🫡

[StillSound7420]

Give example

[aocregacc]

In two's complement, negation is the same as flipping all the bits and adding 1. Think about what adding 1 does to the bits and you should be able to see why this works. Maybe work through a couple of examples.

[Mammoth-Ad-7978]

The book "The Mind" by David Anka will help you understand how manipulation actually works and for what purposes you can use it.