Binary Arithmetic

Recently, there has been a lot of talk about the quantization of LLMs (Large Language Models) to 1-bit. Typically, LLMs operate with float32 or int8 formats, requiring significant computational resources. A BNN (Binary Neural Network), which operates with only a single bit per weight, becomes extremely efficient. It can run on much less powerful hardware because it uses fewer bits, albeit at the cost of some output quality.

In this article, however, I want to take several steps back and try to explain what I have understood about binary arithmetic, which underpins all these complex calculations, starting specifically with addition, subtraction, multiplication, and division.

Definition of Quantization

Quantization means approximating a continuous value to the nearest discrete value, reducing precision in order to achieve benefits such as data compression, space savings, or improved processing speed.

For example, the RGB color model typically uses 256 shades per channel. If I wanted to quantize an image to reduce its size, I would display fewer details and thus fewer shades. If I use only 4 levels (0, 85, 170, 255) instead of 256, a gray pixel originally valued at 123 will become 85 after quantization, as it is the nearest available discrete level.

Note: The standard of 256 levels (8-bit) was historically chosen because it is generally sufficient to create smooth gradients for the human eye. Adding more detailed shades often wouldn't make sense, as the human eye would struggle to perceive the difference.

Understanding Binary Arithmetic

Binary arithmetic is a branch of mathematics that provides the rules for performing mathematical operations using only two digits (0 and 1). This is particularly important because the foundation of all computing lies in electrical circuits that assume only two states: the absence of a signal (0) and the presence of a signal (1).

Performing operations in base 2 is technically more straightforward for logic gates, but it has a steeper learning curve for humans, as we have always been accustomed to working in base 10. The reason humans favor base 10 is simple: we have ten fingers. Historically, lacking abstract methods for counting, early humans found their hands to be the most convenient counting tool.

Binary Operations Overview

• Addition: 0+0=0, 0+1=1, 1+0=1, and 1+1=0 (with a carry of 1).
• Subtraction: Similar to decimal subtraction, utilizing borrows when subtracting 1 from 0.
• Multiplication: Functions like decimal multiplication, but simpler since you only multiply by 1 (copy the number) or 0 (write zeros), followed by binary addition.
• Division: Follows the long division method, checking if the divisor fits into the current bits of the dividend.

Relationship Between Number of Bits and Combinations

Understanding how many combinations can be made with n bits is crucial, as it directly impacts how data is represented in digital systems. Knowing the number of possible combinations helps us grasp the limitations and capabilities of a given system.

The fundamental formula is: Number of combinations = 2ⁿ.

Before diving deeper, a small clarification is needed: in binary, different encoding schemes dictate how these bit combinations are interpreted as actual numbers.

Unsigned System

In an unsigned system, all bit combinations represent non-negative values (starting from 0).

Sign-Magnitude System

When we need to represent negative numbers, one simple method is sign-magnitude representation. In this method, the Most Significant Bit (the first bit on the left) acts as a flag:

• 0 indicates that the number is positive.
• 1 indicates that the number is negative.

While simple for humans to read, this system introduces complexities in hardware calculations (like having a "positive zero" and a "negative zero").

Two’s Complement System

The most common way modern computers represent signed numbers in binary is through the two’s complement system. In two’s complement:

• Positive numbers are represented normally (starting with a 0).
• Negative numbers are obtained by taking the positive value, inverting all the bits (the one's complement), and adding 1 to the result.

This elegant system eliminates the issue of double zeros and allows logic circuits to perform subtraction using the exact same hardware logic used for addition.