6 ms·

Short explanation: 1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x) 2. Crucial observation: -x == ~x + 1 3. ~x flips all th

Short explanation: 1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x) 2. Crucial observation: -x == ~x + 1 3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x & ~x) == 0) 4. When you do +1, all the trailing 1's flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n'th) also flips, becoming 1... like it was in x. 5. Crucial observation: The n'th 0 did NOT match the corresponding bit in x prior to the increment, therefore it MUST match after the increment. All higher bits stay as-is. 6. This leaves only the n'th bits matching in x and ~x + 1, isolating the highest power-of-2 divisor of x when you AND them.

jb1991 2y ago
I thought there was just a sign bit. If not, how does a system know if a number should be interpreted as positive or negative?
- dataflow 2y ago
  Signedness doesn't affect anything here, as long as the representation is in two's complement. The negation of x (i.e. -x) in two's complement is ~x + 1. The interpretation of the bits as signed or unsigned doesn't change any of the following steps.
  - MaxBarraclough 2y ago
    I think strictly speaking signedness does affect things, assuming we're talking C/C++. If x has type int and were to take the value of INT_MIN, then evaluating -x would result in a signed arithmetic overflow, which is undefined behaviour. (Related: the C standard now insists on use of 2's complement, where it used to permit other schemes.) If x had type unsigned int, this wouldn't introduce undefined behaviour.
- elevatedastalt 2y ago
  There's still a sign bit. The sign bit tells you whether to interpret the rest of the number as positive or treat as negative and undo the 2s complement operation.
- eslaught 2y ago
  You're thinking about a sign and magnitude representation, which is not how integers are represented in a modern computer. The modern version is two's complement. It still has a sign bit, but negating a number involves more than just changing the sign bit since the representation is modular. https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Modular_arithmetic https://en.wikipedia.org/wiki/Modular_arithmetic
  - gus_massa 2y ago
    I agree, but I just want to add that floating point numbers use sign and magnitude representation, so the GP may be confused by that.
- cvz 2y ago
  In the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". The reason this has become the most common representation for signed numbers in computer hardware is that it makes the difference between signed and unsigned numbers basically irrelevant as far as the hardware is concerned. When the difference does matter (which it does in division, conversions between different word sizes, conversions to/from text, and sometimes multiplication), there are two different instructions for signed and unsigned, and it's up to the programmer or compiler to pick the right one.
  - thaumasiotes 2y ago
    > n the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". This is only true if the size of your modulus is fixed. In fact, there is a "sign extension" command allowing you to produce, for example, signed 128-bit values from signed 64-bit values, and this basically requires interpreting two's complement values the same way they represent themselves: a three-bit -1 is just the sum of the positive values +1, +2, and +4. To extend that to six bits, you add the positive values +8, +16, and +32. The meaning of the high bit in our six-bit scheme shouldn't be viewed as "when this bit is set, subtract 32 from the value instead of adding it". It is "whether this bit is set or not, all higher bits in the number, the ones that don't exist in the hardware, are equal to it"; under this interpretation, the 8-, 16-, and 32- bits were already set in the three-bit value, and that's why they continue to be set when we do a sign extension. Every place value is still positive, but as long as there is no highest set bit, the number itself will be negative, and equal to the value you'd calculate from its representation as a geometric series.
    - kbolino 2y ago
      This is true mathematically but simple to implement in practice. If the number is signed, shifts to the right and widening casts fill the new bits with a copy of the sign bit. If it's unsigned, shifts to the right and widening casts fill the new bits with zeroes. Shifts to the left and narrowing casts work the same for signed and unsigned.
- pests 2y ago
  2s compliment helps with the problem of otherwise having a +0/-0 and lets you subtract numbers just with adders.
- School-Cotton 2y ago
  Assuming 4-byte integers, 0000 is 0 0001 is 1 0010 is 2 0011 is 3 0100 is 4 0101 is 5 0110 is 6 0111 is 7 1111 is -1 1110 is -2 1101 is -3 1100 is -4 1011 is -5 1010 is -6 1001 is -7 1000 is -8 The highest bit is always 1 when the sign is negative.
  - School-Cotton 2y ago
    Too late to edit, but I meant 4-bit, not 4-byte.
    - fuzztester 2y ago
      What is the edit window in hours?
  - jb1991 2y ago
    Useful example, thanks.
mabster 2y ago
Thanks! I've used the trick and derived why it works a few times, but always forget. I battled to understand the post. Your explanation got me there very quickly.
- dataflow 2y ago
  Sure thing, happy to hear!
pbsd 2y ago
An alternative, more arithmetic, argument: - x is 2^b*k for some odd k < 2^(n-b) - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.
- Droobfest 2y ago
  This immediately reads like gobbledygook to me, while the parent is easy to follow. I’m not trying to dunk on you, but I can’t help to note that the denseness of math is too much for an idiot like me.
  - schoen 2y ago
    It might be nicer with exponents rendered as superscripts, because it could make it more apparent how the exponents are being used.
- chx 2y ago
  > -x is 2^n - 2^b * k Erm no. -x is - 2^b * k and it's the "Two's complement" notation which is 2^n - 2 * b * k This is because the way we generate the "Two's complement" number. Given A in binary representation, let's call A1 the number you get by flipping every bit in A also called one's complement. Observe how every bit in A+A1 is 1 because if the bit was 0 in A then the bit is 1 in A1 and vica versa. So then that's 2^N-1. Two's complement is created by adding 1 to A1 so then A + A1 is 2^N or A1 = 2^N-A. But you do need to prove this before you can use it.
  - bonzini 2y ago
    The point of two's complement is that it's the same as modulo-2^n arithmetic. In two's complement -x is defined such that x + -x = 0 (mod 2^n); and because x + ~x = 2^n - 1 (mod 2^n), then -x = ~x + 1. Therefore x & -x works only in two's complement, and it's fair to assume it as the parent comment did.
arun-mani-j 2y ago
Thanks for the nice summary. I found myself difficult to explain it so I took the help of visual explanation using the bits structure. :)
baryphonic 2y ago
When I read the title, my immediate thought was "because 2s complement!" Your explanation is more thorough.
monktastic1 2y ago
Another, more "visual" description: Without loss of generality, let the number be xx...xx100...000, where x stands for any bit and there are n trailing zeros. 1. The largest power of 2 that divides it is 2^n. 2. The twos-complement representation is xx...xx011...111, where the x's are inverted from before, plus one. 3. After adding one, we get xx...xx100...000. Notice that the carryover stopped exactly where the zero was (which is where our first 1 from the right originally was). 4. All the "x" bits are now inverted from their original values, so their & is zero. All the original trailing zero bits are still zero, so their & is zero. The middle 1 has stayed 1, so its & is 1. 5. Thus, the overall & is 00...00100...000 = 2^n, as required.
- _proofs 2y ago
  this is actually a fantastic comment and as someone who thinks more visually, was greatly appreciated. thank you.
  - dgfitz 2y ago
    Seconded, this comment was hugely valuable to me.
- dataflow 2y ago
  > Without loss of generality, let the number be xx...xx100...000, Note that this is with loss of generality, since there is no guarantee of a 1 bit anywhere in the number ;) but you can handle the zero case specially.
  - monktastic1 2y ago
    "Without loss of much generality..." ;)
oldgradstudent 2y ago
> 2. Crucial observation: -x == ~x + 1 To be annoyingly pedantic, this is not simply an observation, this is essentially the definition of 2's complement arithmetic.
- dataflow 2y ago
  Some people do see it that way, and I think it's fine if you do, but I think I disagree. To me, the definition of N-bit two's complement is that -x (i.e. 0 - x) is represented by 2^N - x. The fact that that is equal to ~x + 1 is not obvious, or (as I see it) part of the definition.
deleted 2y ago
[deleted]
StevenXC 2y ago
Algebraically, where | denotes concatenation, and z is a string of 0s: x = y | 1 | z -x = ~x + 1 -x = (~y | 0 | ~z) + 1 -x = ~y | 1 | z x & -x = (y & ~y) | (1 & 1) | (z & z) x & -x = 0 | 1 | z

jb1991 2y ago

I thought there was just a sign bit. If not, how does a system know if a number should be interpreted as positive or negative?

dataflow 2y ago
Signedness doesn't affect anything here, as long as the representation is in two's complement. The negation of x (i.e. -x) in two's complement is ~x + 1. The interpretation of the bits as signed or unsigned doesn't change any of the following steps.
- MaxBarraclough 2y ago
  I think strictly speaking signedness does affect things, assuming we're talking C/C++. If x has type int and were to take the value of INT_MIN, then evaluating -x would result in a signed arithmetic overflow, which is undefined behaviour. (Related: the C standard now insists on use of 2's complement, where it used to permit other schemes.) If x had type unsigned int, this wouldn't introduce undefined behaviour.
elevatedastalt 2y ago
There's still a sign bit. The sign bit tells you whether to interpret the rest of the number as positive or treat as negative and undo the 2s complement operation.
eslaught 2y ago
You're thinking about a sign and magnitude representation, which is not how integers are represented in a modern computer. The modern version is two's complement. It still has a sign bit, but negating a number involves more than just changing the sign bit since the representation is modular. https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Modular_arithmetic https://en.wikipedia.org/wiki/Modular_arithmetic
- gus_massa 2y ago
  I agree, but I just want to add that floating point numbers use sign and magnitude representation, so the GP may be confused by that.
cvz 2y ago
In the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". The reason this has become the most common representation for signed numbers in computer hardware is that it makes the difference between signed and unsigned numbers basically irrelevant as far as the hardware is concerned. When the difference does matter (which it does in division, conversions between different word sizes, conversions to/from text, and sometimes multiplication), there are two different instructions for signed and unsigned, and it's up to the programmer or compiler to pick the right one.
- thaumasiotes 2y ago
  > n the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". This is only true if the size of your modulus is fixed. In fact, there is a "sign extension" command allowing you to produce, for example, signed 128-bit values from signed 64-bit values, and this basically requires interpreting two's complement values the same way they represent themselves: a three-bit -1 is just the sum of the positive values +1, +2, and +4. To extend that to six bits, you add the positive values +8, +16, and +32. The meaning of the high bit in our six-bit scheme shouldn't be viewed as "when this bit is set, subtract 32 from the value instead of adding it". It is "whether this bit is set or not, all higher bits in the number, the ones that don't exist in the hardware, are equal to it"; under this interpretation, the 8-, 16-, and 32- bits were already set in the three-bit value, and that's why they continue to be set when we do a sign extension. Every place value is still positive, but as long as there is no highest set bit, the number itself will be negative, and equal to the value you'd calculate from its representation as a geometric series.
  - kbolino 2y ago
    This is true mathematically but simple to implement in practice. If the number is signed, shifts to the right and widening casts fill the new bits with a copy of the sign bit. If it's unsigned, shifts to the right and widening casts fill the new bits with zeroes. Shifts to the left and narrowing casts work the same for signed and unsigned.
pests 2y ago
2s compliment helps with the problem of otherwise having a +0/-0 and lets you subtract numbers just with adders.
School-Cotton 2y ago
Assuming 4-byte integers, 0000 is 0 0001 is 1 0010 is 2 0011 is 3 0100 is 4 0101 is 5 0110 is 6 0111 is 7 1111 is -1 1110 is -2 1101 is -3 1100 is -4 1011 is -5 1010 is -6 1001 is -7 1000 is -8 The highest bit is always 1 when the sign is negative.
- School-Cotton 2y ago
  Too late to edit, but I meant 4-bit, not 4-byte.
  - fuzztester 2y ago
    What is the edit window in hours?
- jb1991 2y ago
  Useful example, thanks.

mabster 2y ago

Thanks! I've used the trick and derived why it works a few times, but always forget. I battled to understand the post. Your explanation got me there very quickly.

dataflow 2y ago
Sure thing, happy to hear!

pbsd 2y ago

An alternative, more arithmetic, argument: - x is 2^b*k for some odd k < 2^(n-b) - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.

Droobfest 2y ago
This immediately reads like gobbledygook to me, while the parent is easy to follow. I’m not trying to dunk on you, but I can’t help to note that the denseness of math is too much for an idiot like me.
- schoen 2y ago
  It might be nicer with exponents rendered as superscripts, because it could make it more apparent how the exponents are being used.
chx 2y ago
> -x is 2^n - 2^b * k Erm no. -x is - 2^b * k and it's the "Two's complement" notation which is 2^n - 2 * b * k This is because the way we generate the "Two's complement" number. Given A in binary representation, let's call A1 the number you get by flipping every bit in A also called one's complement. Observe how every bit in A+A1 is 1 because if the bit was 0 in A then the bit is 1 in A1 and vica versa. So then that's 2^N-1. Two's complement is created by adding 1 to A1 so then A + A1 is 2^N or A1 = 2^N-A. But you do need to prove this before you can use it.
- bonzini 2y ago
  The point of two's complement is that it's the same as modulo-2^n arithmetic. In two's complement -x is defined such that x + -x = 0 (mod 2^n); and because x + ~x = 2^n - 1 (mod 2^n), then -x = ~x + 1. Therefore x & -x works only in two's complement, and it's fair to assume it as the parent comment did.

arun-mani-j 2y ago

Thanks for the nice summary. I found myself difficult to explain it so I took the help of visual explanation using the bits structure. :)

baryphonic 2y ago

When I read the title, my immediate thought was "because 2s complement!" Your explanation is more thorough.

monktastic1 2y ago

Another, more "visual" description: Without loss of generality, let the number be xx...xx100...000, where x stands for any bit and there are n trailing zeros. 1. The largest power of 2 that divides it is 2^n. 2. The twos-complement representation is xx...xx011...111, where the x's are inverted from before, plus one. 3. After adding one, we get xx...xx100...000. Notice that the carryover stopped exactly where the zero was (which is where our first 1 from the right originally was). 4. All the "x" bits are now inverted from their original values, so their & is zero. All the original trailing zero bits are still zero, so their & is zero. The middle 1 has stayed 1, so its & is 1. 5. Thus, the overall & is 00...00100...000 = 2^n, as required.

_proofs 2y ago
this is actually a fantastic comment and as someone who thinks more visually, was greatly appreciated. thank you.
- dgfitz 2y ago
  Seconded, this comment was hugely valuable to me.
dataflow 2y ago
> Without loss of generality, let the number be xx...xx100...000, Note that this is with loss of generality, since there is no guarantee of a 1 bit anywhere in the number ;) but you can handle the zero case specially.
- monktastic1 2y ago
  "Without loss of much generality..." ;)

oldgradstudent 2y ago

> 2. Crucial observation: -x == ~x + 1 To be annoyingly pedantic, this is not simply an observation, this is essentially the definition of 2's complement arithmetic.

dataflow 2y ago
Some people do see it that way, and I think it's fine if you do, but I think I disagree. To me, the definition of N-bit two's complement is that -x (i.e. 0 - x) is represented by 2^N - x. The fact that that is equal to ~x + 1 is not obvious, or (as I see it) part of the definition.

deleted 2y ago

[deleted]

StevenXC 2y ago

Algebraically, where | denotes concatenation, and z is a string of 0s: x = y | 1 | z -x = ~x + 1 -x = (~y | 0 | ~z) + 1 -x = ~y | 1 | z x & -x = (y & ~y) | (1 & 1) | (z & z) x & -x = 0 | 1 | z