61–67 of 67 posts
Earlier quoted context omitted.
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?
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.
Earlier quoted context omitted.
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.
Too late to edit, but I meant 4-bit, not 4-byte.
just like in decimal: 70 is divisible by 10, 500 is divisible by 100,
so in binary 10 is divisible by 2 10100 is divisible by 4 101010111000 is divisible by 8 etc. (We also know 101010111001 can't be divisible by 8, cause it's only 1 more than a number divisible by 8)
Knowing this we can look at the question backwards take 24 and -24, because 24 is divisible by 8 it must end with a 1 and 3 0s ...0011000
when we take the compliment we get 1100111 which for the same reason must end in a 0 and a run of 1s,
now when we add one to this, all the ones will roll over and we end up with the same tail "1000" as in 24, and since this anything to the left of the tail is a compliment of the corresponding bit in x a bitwise and will just be the tail.
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. Cruci…
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 zer…
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.
To take this to the next level: what does [(a^b) & (-(a^b)) & a] compute? (Assume unsigned arithmetic.) And then after that: what use can this be put to?
It (using the address of the nodes as arguments) can serve as a tiebreaker in a Cartesian tree (such as one implementing a first-fit memory allocator) or even to replace the random priority value in a treap (meaning you need neither storage nor computation for the priority node of the treap).
Earlier quoted context omitted.
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 zer…
> 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.