# Binary system

## Conversions

### Conversion from binary to hex

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

BinaryHex
00011
00102
00113
01004
01015
01106
01117
10008
10019
1010A
1011B
1100C
1101D
1110E
1111F

### 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 2Hex
2^01
2^12
2^24
2^38
2^410
2^520
2^640
2^780
2^8100
2^9200
2^10400
2^11800
2^121000
2^132000
2^144000

## 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 of an n-digit number in radix is the difference between and .

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

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:

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:

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

#### 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):