Bitwise Operation

Bitwise operations

NOT operation (~)

Flip all bits: $0 \rightarrow 1$, $1 \rightarrow 0$. In a 32-bit system,

Negate (-)

To negate a number $x$, computer does

In Java, the range of Integer is $[-2^{31}, 2^{31}-1]$. Negating the most negative integer $-2^{31}$ overflows and wraps around to itself.

- Integer.MIN_VALUE == Integer.MIN_VALUE

Mathematically, in 2’s complement system,

   ~ 0  == -1
   ~ -1 == 0
   ~ 1  == -2
   ~ -5 == 4
   ~ 6  == -7
   ~ Integer.MIN_VALUE == Integer.MAX_VALUE
   ~ Integer.MAX_VALUE == Integer.MIN_VALUE 

Alignment Rounding

One of the most common bit-manipulation idioms in low-level systems programming.

Like round $x$ up to the next multiple of pagesize.

E.g.

    assertEquals(8192, 5000 + ((1 << 12) - 1) & ~ ((1 << 12) - 1));
    assertEquals(8192, Math.ceilDiv(5000, 1 << 12) * (1 << 12));

Two’s complement

In Java, the range of signed integer is $[-2^{31}, 2^{31}-1]$,

Even if x is the most negative integer, it still holds because

- Integer.MIN_VALUE == Integer.MIN_VALUE

$\texttt{Integer.toUnsignedLong(int)}$

Mathematically,

For example, $\texttt{toUnsignedLong}(-5) = -5 + 2^{32} = 4294967291$

In Java, it just reinterpret the signed integer as an unsigned one, the result is returned as a long in the range $[0, 2^{32}-1]$

Integer.toUnsignedLong(x) = 0xffffffffL & x

Arithmetic shift (>>) and logical shift (>>>, <<)

There is only arithmetic right shift, no arithmetic left shift. Because the sign bit is the leftmost bit, whether replicate it to fill the new leftmost empty bit is only relevant to right shift.

Arithmetic right shift (>>)

• Floored division, rounds toward -∞.
• Preserves the sign.
• Fills new leftmost with the sign bit.

x >> n == Math.floorDiv(x, 1 << n) == Math.floor((double)x / (1 << n))

int Math.floorDiv(x, y) {
  int q = x / y;
  // if the signs are different and modulo not zero, round down
  if ( (x ^ y) < 0 && q * y != x ) {
    return q - 1;
  }
  return q;
}

Math.floorDiv(x, y) == Math.floor((double) x / y)

-7 >> 1 == -4               // round toward -∞
-7 >> 2 == -2               // round toward -∞
-8 >> 1 == -4

Division (/)

• Truncated division (fraction part truncated), rounds toward 0.
• Preserves the sign

-7 / 2 = -3                 // truncate the fraction part
-7 / 4 = -1                 // truncate the fraction part

Logical right shift (>>>)

• Always treats number as unsigned
• Fills new leftmost with 0

Mathematically, x >>> n is equivalent to

// NOTE:
// 1. 1L << n
// 2. cast the reuslt of long integer devision back to int
(x >= 0) ? x / (1 << n) : (int)(Integer.toUnsignedLong(x) / (1L << n))

Logical left shift (<<)

• Fills new rightmost with 0

Mathematically, regardless of whether $x$ is positive or negative, the operation is equivalent to:

0 << 5 == 0
1 << 4 == 16
-1 << 4 == -16
Integer.MIN_VALUE << 1 == 0
Integer.MAX_VALUE << 1 == -2
(Integer.MIN_VALUE+1) << 1 == 2