Conversion from binary to hex
Given a binary number, group its digits in groups of 4, then replace according to the below table:
Conversion from binary to octal
Similarly, it’s possible to convert a binary number to octal by grouping the digits in groups of 3:
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:
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:
In binary, the radix complement is called the two’s complement and the diminished radix complement the ones’ complement.
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
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
Signed integers in ones’ complement
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.
signed integers in two’s complement:
signed integers in ones complement:
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
The operator, , is an exclusive or and verifies the following identities:
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: