Haonan's blog

Bits, Bytes, and Integers I

 
  • Jun 09, 2023

In this and next couple of blogs, we gonna talking about data representations, how numbers are represented in different forms and some of the properties. We need to understand what is the bit level representation of numbers and how does that affect some of the properties when we operate them on. Especially, we need to pay attention to these corner cases.

Encoding Byte Values

We commonly group collections of 4 bits at a time, and represent that in base 16 (hexadecimal representation, ${ 1,2,\cdots,9,A,B,\cdots, F }$). Using the letters A throught F as values 10 through 15. In C, numeric constants starting with 0x or 0X are interpreted as being in hexadecimal. For example, we could write the number ${ \text{FA1D37B}_{16} }$ as 0xFA1D37B, as 0xfa1d37b, or even mixing upper- and lowercase (e.g., 0xFa1D37b). Note, if the total number of bits is not a multiple of 4, you should make the leftmost group be the one with fewer than 4 bits, effectively padding the number with leading zeros. Then you translate each group of bits into the corresponding hexadecimal digit, like 110010, we will pad it as 00110010, that is 0x32.

Most computers use blocks of 8 bits, or bytes, as the smallest addressable unit of memory. A machine-level program views memory as a very large array of bytes, referred to as virtual memory. Every byte of memory is identified by a unique number, known as its address, and the set of all possible addresses is known as the virtual address space.

In fact, this virtual address space is just a conceptual image presented to the machine-level program. The actual implementation uses a combination of dynamic random access memory (DRAM), flash memory, disk storage, special hardware, and operating system software to provide the program with what appears to be a monolithic byte array, which will be talked in latter class.

Boolean Algebra

  • And A&B = 1, when both A = 1 and B = 1

  • Or A|B = 1, when either A = 1 or B = 1
  • Not ~A = 1, when A = 0
  • Exculsive-Or (Xor) A^B = 1, when A,B are different

Here is a Example, we can use 8 bits to represent a set ${ A }$, the element is ${ 0,\cdots,7 }$. ${ a_j = 1 }$ if ${ j \in A}$. Let’s give two sets ${ A_1={0，3，5，6}, A_2={0,2,4,6} }$, we represent it as

$$ \begin{equation} \begin{aligned} &01101001 &A_1 = \{0,3,5,6\}\\ &~~65~~3~~~~0 &\\ \end{aligned} \end{equation} $$
$$ \begin{equation} \begin{aligned} &01010101 &A_2 = \{0,2,4,6\}\\ &~~6~~4~~2~~0 &\\ \end{aligned} \end{equation} $$

And, the Boolean operations can have some specific meaning

  • & Intersection 01000001 {0,6}
  • | Union 01111101 {0,2,3,4,5,6}
  • ^ Symmetric difference (all the unique elements in each set) {2,3,4,5}
  • ~ Complement 10101010 {1,3,5,7}

Contrast: Logic Operations in C

Actually, &&, ||, ! (exclamation mark, or is pronounced as “bang”) have different meaning with &, |, ~ in C. They are logic operation rather than bit operation.

For &&, ||, !, they have following properties

  • View 0 as “Flase”
  • Anything nonzero as “True”
  • Always return 0 or 1
  • Early termination

    (&& and || can be treat as a “lazy” operation, like && will terminate and return 0, when it finds the first element is 0, it doesn’t check the following one. Similarly, || will terminate and return 1 when it check the first element is 1.)

Here are some examples (char data type)

  • !0x41 ${ \rightarrow }$ 0x00 (0x41 is a nonzero bit pattern, so it represents True. Thus, !0x41 = Flase = 0x00)
  • !0x00 ${ \rightarrow }$ 0x01

  • !!0x41 ${ \rightarrow }$ 0x01

  • 0x69 && 0x55 ${ \rightarrow }$ 0x01 (True && True ${ \rightarrow }$ True = 0x01)
  • 0x69 || 0x55 ${ \rightarrow }$ 0x01 (True || True ${ \rightarrow }$ True = 0x01)
  • p && *p (By early termination, we can avoid null pointer access)

Shift Operation

  1. Left Shift: x « y

    Shift bit-vector ${ x }$ left ${ y }$ position.

    • Throw away extra bits on left
    • Fill with 0’s on right

  2. Right Shift: x » y

    Shift bit-vector ${ x }$ right ${ y }$ position. Throw away extra bits on right, but for filling on left we have two different way

    • Logical shift: Fill with 0’s on left
    • Arithmetric shift: Replicate most significant bit on left

Take an example, x = 01100010, x » 2

First, we throw away the rightmost two bits, and empty the leftmost two bits as ${ \Box \Box 011000}$. The second step, for logical way, we get 00011000, and for arithmetric way, we get 00011000 too, because the leading number of remaining part is 0 (011000).

Take another example, x = 10100010, x » 2.

In this case, we get ${ \Box \Box 100010}$ at first step. So, the most significant bit on left is 1. Therefore, the Arithmetric shift gets 11101000.

Ok, let us think about following case, what should we get if we left shift x by 8 bits? x is a byte here. Will we get 00000000? No, we will get x whatever x is. Because, x « y actually do x « y’, here y’ = y mod 8 (In practice, we just need to reserve the leftmost 3 bits, and ignore the higher bits, we can achieve same effect as “mod 8”).

Intergers

How we encoding intergers, for Unsigned number, we have following equation (B2U: bits to Unsigned), ${ w }$ denotes word-size here

$$ B2U(X) = \sum_{i=0}^{w-1} x_i \cdot 2^i $$

That’s easy to understand, we just add all the value in each bit.

For «i>b>Two’s Complement</b></i>, that can represent negative number, we have this equation, (B2T: bits to Two’s Complement)

$$ B2T(X) = - x_{w-1} \cdot 2^{w_1} + \sum_{i=0}^{w-2} x_i \cdot 2^i $$

In this case, most significant bit indicates sign

  • 0 for non-negative
  • 1 for negative

Here is a example like ${ 10110 }$, for Two’s Complement it’s value is ${ -1\cdot 16 + 0\cdot 8 + 1\cdot 4 + 1 \cdot 2 + 0\cdot 1 = -10}$.

Then let check the numberic ranges.

For unsigned values, the largest case is all the bits are 1, and the smallest case is all the bits are 0

$$ \begin{equation} \begin{aligned} U_{min} &= 00 \dots 0_{2}= 0 \\ U_{max} &= 11 \dots 1_{2} = 2^w -1 \\ \end{aligned} \end{equation} $$

For the Two’s complement, the largest case is the sign bit is 0, and other bits are all 0, the smallest case is sign bit is 1, and other bits are all 1

$$ \begin{equation} \begin{aligned} T_{min} &= 10 \dots 0_{2}= - 2^{w-1} \\ T_{max} &= 01 \dots 1_{2} = 2^w -1 \\ \end{aligned} \end{equation} $$

So, for a same bit pattern ${ x }$, the signed value and unsigned value can build a mapping. That is

$$ \begin{equation} B2U(x) = \begin{cases} & B2T(x) + 2^w, & B2T(x) < 0 \\ & B2T(x) , & B2T(x) \geq 0 \end{cases} \end{equation} $$

Vice versa

$$ \begin{equation} B2T(x) = \begin{cases} & B2U(x) - 2^w, & B2U(x) > T_{max} \\ & B2U(x) , & B2U(x) \leq T_{max} \end{cases} \end{equation} $$

Signed vs. Unsigned in C

By default, numbers are considered to be signed integers in C. U as a suffix represents this is an unsigned value. So, numbers will be treat as unsigned when have ‘U’ as suffix.

Casting

  • Explicit casting between signed & unsigned
1
2
3
4

    int tx, ty;
    unsigned ux, uy;
    tx = (int) ux; /* casting unsigned ux to signed */
    uy = (unsigned) ty; /* casting signed ty to unsigned */
  • Implicit casting also occurs via assignments and procedure calls
1
2
3
4

    int tx, ty;
    unsigned ux, uy;
    tx = ux; /* casting unsigned ux to signed */
    uy = ty; /* casting signed ty to unsigned */

1
2

    int fun(unsigned u);
    uy = fun(tx);

Attention!!! If there is a mix of unsigned and signed value in a single expression,

sigend values implicitly cast to unsigned

Like compare ${ -1 }$ and ${ 0U }$, we will transfer it to bit representation as ${ 11\dots 1, 00\dots 0 }$. So, ${ -1 > 0U }$.

If both operands are signed (or unsigned), the comparison is same to the arithmetric operation.

Expending the Bit representation

Suppose you have a number represented in 8 bits, but now you want to represent it in 16 bits. What we should do to modify the bit pattern and maintain the original value of the number.

In fact, for unsigend number, it’s easy to accomplish. We just need to pad 0 in the extra bits in the left. How about signed integer?

Task:

  • Given ${ w }$-bit signed integer ${ x }$
  • Convert it to ${ w+k }$-bit integer with same value

If the leading bit of ${ x }$ is 0, we just keep it and adding zero in the extra left bits.

If the leading bit is 1, we can just make ${ k }$ copies of 1 in the left first extra ${ k }$ bits. Why is that? We can check it. The sum of left extra ${ k }$ bits is

$$ \begin{equation} \begin{aligned} \text{Sum of first k bits} &= 2^{w-1} + 2^{w} + \cdots + 2^{w+k-2} -2^{w+k-1} \\ &= 2^{w-1} \cdot (1 + 2 + \cdots + 2^{k-1} - 2^{k}) \\ & = 2^{w-1} \cdot (2^k - 1 - 2^k) \\ & = -2^{w-1} \end{aligned} \end{equation} $$

That’s exactly equals to the value of original leading bit ${ -2^{w-1} }$.

Therefore, summary the two cases, for signed integer, we can do the bit extension by the following rule

Rule:

  • Make k copies of sign bit (no matter the leading bit is 0 or 1)
  • The new bit pattern ${ X’= \underbrace{x_{w-1},\dots,x_{w-1},}_{k \text{ copies}} x_{w-1}, x_{w-2},\dots,x_0}$

In the end, given a unsigned number ${ x }$, if we truncate it, like just keep the right four bits. What’s gonna happen? Actually, it does the mod operation. Like keeping right four bits is doing “${ x }$ mod ${ 16 }$”. In fact, when we keep right ${ k }$ bits, we are doing ${ x }$ mod ${ 2^k }$.

Search