bitwise operations with negative numbers

[AndrewShort]

I am finally ready to make my hash entries more compact, and for starters, I'm going to combine the score and depth searched and score type into 4 bytes, which is plenty of room. [My starting goal is to get down to 16 bytes, then later I'll get it down to 12 bytes.]

Anyway, to combine the score with other bits is interesting, because the score can be positive or negative. I was playing around in VB.NET with And, Or, and Shift with positive and negative numbers, and I understand most of the results but not the last section:

4 >> 1 = 2
4 >> 2 = 1
4 << 1 = 8
4 << 2 = 16

-4 >> 1 = -2
-4 >> 2 = -1
-4 << 1 = -8
-4 << 2 = -16

4 And 12 = 4
4 And 6 = 4
4 Or 12 = 12
4 Or 6 = 6

-4 And 12 = 12 [why??]
-4 And 6 = 4
-4 Or 12 = -4 [why??]
-4 Or 6 = -2 [why??]

I don't understand the 3 marked [why?] above.... Can someone englighten me?

[Zach Wegner]

That's because of the two's complement: http://en.wikipedia.org/wiki/Two's_complement

To properly store negative numbers in a hash table by compacting the bits, you need to add an offset to make the number positive before doing any bitwise arithmetic, and then subtract it back when you take the number out.

[AndrewShort]

oh I see. you mean add, say, iINFINITY to the score before setting the score bits, then after reading the score bits, subtract iINFINITY (where - iINFINITY the most negative score that would ever want to be stored). that makes sense, thanks.

[Dann Corbit]

6.5.7 Bitwise shift operators
Syntax
1 shift-expression:
additive-expression
shift-expression << additive-expression
shift-expression >> additive-expression
Constraints
2 Each of the operands shall have integer type.
Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 * 2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 * 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

[Gerd Isenberg]

I understand most of the results but not the last section:

-4 And 12 = 12 [why??]
-4 And 6 = 4
-4 Or 12 = -4 [why??]
-4 Or 6 = -2 [why??]

I don't understand the 3 marked [why?] above.... Can someone englighten me?

writing negative numbers as binaries or hex makes it more clear:

Code: Select all

11111100 & 00001100 = 00001100 -> 0xFC & 0x0C = 0x0C
11111100 & 00000110 = 00000100 -> 0xFC & 0x06 = 0x04
11111100 | 00001100 = 11111100 -> 0xFC | 0x0C = 0xFC
11111100 | 00000110 = 11111110 -> 0xFC | 0x06 = 0xFE

Note in twos' complement, you copy from low to high until first binary one, then invert remaining upper bits:

Code: Select all

00000100  4
11111100 -4

11111110 -2
00000010  2

Gerd

[bob]

I am finally ready to make my hash entries more compact, and for starters, I'm going to combine the score and depth searched and score type into 4 bytes, which is plenty of room. [My starting goal is to get down to 16 bytes, then later I'll get it down to 12 bytes.]

Anyway, to combine the score with other bits is interesting, because the score can be positive or negative. I was playing around in VB.NET with And, Or, and Shift with positive and negative numbers, and I understand most of the results but not the last section:

4 >> 1 = 2
4 >> 2 = 1
4 << 1 = 8
4 << 2 = 16

-4 >> 1 = -2
-4 >> 2 = -1
-4 << 1 = -8
-4 << 2 = -16

4 And 12 = 4
4 And 6 = 4
4 Or 12 = 12
4 Or 6 = 6

-4 And 12 = 12 [why??]
-4 And 6 = 4
-4 Or 12 = -4 [why??]
-4 Or 6 = -2 [why??]

I don't understand the 3 marked [why?] above.... Can someone englighten me?

sure. -4 is FFFFFFFC in base 16. 12 = 0000000C in base 16. And them and you get 0000000C

You don't want to use negative numbers. The solution is to bias the numbers by a positive value large enough to ensure you do not end up with a negative number. Then when you extract the number you subtract the bias to restore it to its original value.