Everything is bits

The whole digital world is sort of based on binary values. (but in fact the first electronic computer the ENIAC built in University of Pennsylvania basically encoded did all of its arithmetic using base ten)

Advantages of using bit

  • Easy to store with bitsable elements
  • Reliably transmitted on noisy and inaccurate wires(if low range of voltage means 0 and high range of values means 1, if there’s noise or imperfections in the circuit or anything going on, as long as that doesn’t exceed these bit these thresholds you’ve set up, then you will get a nice clean signal out of it)

Boolean Algebra

An example of representing & manipulating sets:

Width w bit vector represents subsets of {0, …, w - 1},

Representation:

  • 01101001 {0, 3, 5, 6}

  • 76543210

  • 01010101 {0, 2, 4, 6}

  • 76543210

Operations:

  • & Intersection 01000001 {0, 6}
  • | Union 01111101 {0, 2, 3, 4, 5, 6}
  • ^ Symmetric difference 00111100 {2, 3, 4, 5}
  • ~ Complement 10101010 {1, 3, 5, 7}

Contrast: bitwise Operations and Logic Operations

&&, ||, !: view 0 as “false”, anything nonzero as “True”, always return 0 or 1, Early termination.

Obviously this is a very different operations.

If we want to make sure that not accessing a null pointer, we can test whether that’s a null pointer first before accessing it.

Anyway, DON’T MIX THESE UP!

Shift Operations

Also a class of operations.

A left shifts are always the same, but there’s two different flavors of right shift.

Left Shift: x << y

Shift bit-vector x left y positions. Throw away extra bits on left, fill with 0’s on right.

The upper positions of that original words will disappear.

Right Shift: x >> y

Shift bit-vector x right y positions. Throw away extra bits on right.

  • Logical shift: Fill with 0’s on left.
  • Arithmetic shift: Replicate most significant bit(MSB, also called the high-order bit) on left.
Argument x 01100010 10100010
Log. >> 2 00011000 00101000
Arith. >> 2 00011000 11101000

Number Ranges

Unsigned Values

UMin=0UMin = 0, UMax=2w1UMax = 2^w - 1

such as five bit numbers,

If bit positions are all zeros, the number is equal zero, and if it’s all 1 it will be 16 + 8 + 4 + 2 + 1 = 31.

Two’s Complement Values

Which is a way to represent both negative and positive numbers, the most significant bit is the sign bit.

TMin=2w1TMin = -2^{w-1}, TMax=2w11TMax = 2^{w - 1} - 1

The smallest number is 10000 = -16, the largest is 011111 = 15.

Encoding Integers

Bit pattern is maintained,but reinterpreted

Unsigned

B2U(X)=i=0w1xi2iB2U(X)=\sum^{w-1}_{i=0}x_i\cdot2^i

Two’s Complement

B2T(X)=xw12w1+i=0w2xi2iB2T(X)=-x_{w-1}\cdot2^{w-1}+\sum^{w-2}_{i=0}x_i\cdot2^i

Sign Bit

For Two’s Complement, most significant bit indicates sign

  • 0 for nonnegative
  • 1 for negative

Unsign & Signed Numberic Values

When the higher bit is 0 will be the same in both cases.

We can make up a rule converting between two’s complement number X and an unsigned number UX.(T2U, U2T)

Process

T2U: T2B - B2U, U2T: U2B - B2T.

Casting Surprises In C

1.

If there is a mix of unsigned and signed in single expression, signed values implicitly cast to unsigned, including comparison operations <, >, ==, <=, >=

1
2
3
4
5
int main() {
int a = -1; //bit pattern: 1111...1, then B2U is UMax
unsigned int b = 0; //bit pattern: 0000...0, whitch is UMin
cout << (a > b); //UMax > UMin
} //output: 1
1
2
3
4
5
int main() {
int a = 2147483647;
unsigned int b = 2147483648;
cout << (a < b) << " " << (a > (int)b);//the former is cast to unsigned, the latter is not.
}// output: 1 1

All in all, if both of them are signed, then it’ll treat them as a signed case, if either of them is unsigned, then it’ll convert then other one to be an unsigned number and do the operation.

2.

1
2
3
4
5
6
7
8
int main() {
int x;
cin >> x; //TMin: -0x7fffffff - 1
if (x < 0) return -x; //-TMin: 0x7fffffff + 1, whitch is 0111...1 + 1 = 1000...0 = TMin.
else return x;
//input: TMin
//output: TMin
}

TMin=TMax+1|TMin| = |TMax| + 1, UMax=2Tmax+1UMax = 2\cdot Tmax + 1

As for the latter, here is one way to think about it.

TMax is a zero followed by a bunch of ones, And if we want to double that number position, we can shift it left by one position, and end up with a zero, then add one, then we get UMax.

3.

1
2
3
4
5
6
int main() {
int i;
for (i = 3; i - sizeof(char) >= 0; i--) {
cout << i << " ";
}
}//output: 3 2 1 0 -1 -2 -3 -4 ...

The result of sizeof is considered to beunsigned, so it’ll turn treat the combination of the two is unsigned.

Sign Extension

Task:

Given w-bit signed integer x, convert it to w+kbitw + k - bit integer with same value

Rule:

Make k copies of sign bit.

Example:

0110: just add a zero to the lead: 00110.

1110: make a copy of sign bit: 11110.

Principle

Continue using the example described above, the old sign bit had a weight of -8, the new sign bit has a weight of -16, but converted that old sign bit into a positive number which is +8, and we combine -16 and +8 we will still get a -8,we don’t change the net effect of the sum.