## Conversions

### Conversion from binary to hex

Given a binary number, group its digits in groups of 4, then replace according to the below table:

Binary | Hex |
---|---|

0001 | 1 |

0010 | 2 |

0011 | 3 |

0100 | 4 |

0101 | 5 |

0110 | 6 |

0111 | 7 |

1000 | 8 |

1001 | 9 |

1010 | A |

1011 | B |

1100 | C |

1101 | D |

1110 | E |

1111 | F |

#### Proof

### Conversion from binary to octal

Similarly, it’s possible to convert a binary number to octal by grouping the digits in groups of 3:

### Powers of 2 in hex

Powers of 2 | Hex |
---|---|

2^0 | 1 |

2^1 | 2 |

2^2 | 4 |

2^3 | 8 |

2^4 | 10 |

2^5 | 20 |

2^6 | 40 |

2^7 | 80 |

2^8 | 100 |

2^9 | 200 |

2^10 | 400 |

2^11 | 800 |

2^12 | 1000 |

2^13 | 2000 |

2^14 | 4000 |

## Mnemonics

For any base , equals 1 followed by zeros:

equals times the digit :

has the same representation in any base:

Multiplying by equates to shifting the digits one place to the left:

Integer division by equates to shifting the digits one place to the right:

equates to keeping the least significant digits:

## Numeric complements

### Radix complement

Radix complement of an n-digit number in radix is the difference between and .

If is a n-digit number, then radix complement, , is , e.g.

### Diminished radix complement

Diminished radix complement is radix complement minus 1,

The advantage of using over is its simplicity to calculate: just replace each digit for its corresponding , e.g.

In a binary representation, it’s even easier as the calculation of the is equivalent to flipping zeros and ones:

(1)

#### Proof

(2)

Resulting:

In binary, the radix complement is called the **two’s complement **and the diminished radix complement the **ones’ complement**.

### Negative numbers

Radix and diminished radix complements are used to represent negative numbers. Given a range of unsigned numbers , the subinterval corresponds to positive numbers and the subinterval to negative numbers. Any represents the negative value of its radix or diminished radix (depending on the convention used) complement. This way subtractions can be handled as additions without needing to deal with the sign of the negative numbers.

For instance, when using the radix complement in the interval , the negative values are:

and therefore, the numbers represented by the elements of are:

If instead we use diminished radix complement, the negative values are:

and the numbers that can be represented are:

From the above results, it follows that given the interval of unsigned numbers , the corresponding interval of signed numbers is:

- in radix complement
- in diminished radix complement

For the particular case of the binary system:

- in two’s complement
- in ones’ complement

### Integer arithmetic

Let’s consider now how to add/subtract numbers in a given range. In general, given the range of unsigned numbers , the result of adding up 2 numbers is in the range , that exceeds the original range. In order to avoid overflowing and keep in the original range, it is necessary to calculate .

For instance, with 4-bit integers, we can represent:

- unsigned numbers in the range
- signed numbers in two’s complement in the range
- signed numbers in ones’ complement in the range

#### Unsigned integers

#### Signed integers in two’s complement

(positive overflow)

(negative overflow)

#### Signed integers in ones’ complement

(positive overflow)

(negative overflow)

## Bitwise operators

### Invert operator

The unary (invert) operator yields the bitwise inversion of its integer argument (in the binary system that is equivalent to calculate the ones’ complement). The interpretation of the result depends on the number of bits used to represent the integer and whether it is signed or unsigned.

unsigned integers:

signed integers in two’s complement:

signed integers in ones complement:

#### Java examples

In Java, the *byte* data type is an 8-bit signed two’s complement integer. It has a minimum value of -128 and a maximum value of 127.

jshell> (byte)(-128-1) $131 ==> 127 jshell> (byte)(127+3) $132 ==> -126 jshell> ~127 $134 ==> -128

### Xor operator

The operator, , is an exclusive or and verifies the following identities:

Therefore:

This property, plus the fact that is associative, allows to solve the following problem with a single loop:

Given an array of integers, find the one that appears an odd number of times.

There will always be only one integer that appears an odd number of times

from operator import xor from functools import reduce def find(seq): return reduce(xor, seq)

also verifies these identities (provided 2’s complement is used to represent negative integers):