Borrow and Carry Bit for Subtraction

Similar to the usage of the carry bit when adding there are mechanisms for subtracting that allow to integrate the result of subtraction of the lower bits into the subtraction of the next higher block of bits, where necessary. There are two ways to do this, that are trivially equivalent by a simple not operation: […]

Share Button

How to draw lines, circles and other curves

These ideas were developed more than 30 years without knowing that they were already known at that time… Today the graphics cards can easily do things like this in very little time. And today’s CPUs are of course really good at multiplying. So this has lost a lot of its immediate relevance, but it is […]

Share Button

Carry Bit, Overflow Bit and Signed Integers

It has already been explained how the Carry Bit works for addition. Now there was interest in a comment about how it would work for negative numbers. The point is, that the calculation of the carry bit does not have any dependency on the sign. The nature of the carry bit is that it is […]

Share Button

How to multiply long numbers

Assuming we have a multiplication of n-bit-numbers already available. Other than typical compiled languages, which assume that the multiplication result fits into the same size as the two factors, we should take a closer look. Unsigned n-bit-numbers as factors and fullfill         So we have for the product     So we […]

Share Button

How to recover the Carry Bit

As frequent readers might have observed, I like the concept of the Carry Bit as it allows for efficient implementations of long integer arithmetic, which I would like to use as default integer type for most application development. And unfortunately such facilities are not available in high level languages like C and Java. But it […]

Share Button

Shift- and Rotation Functions

Deutsch In a comment to Carry Bit: How does it work the question about shift and rotation functions has been asked. Which exist and how they work exactly depends off course on the CPU architecture, but I will try to give a high level overview anyway. The following aspects have to be considered: 8, 16, […]

Share Button

Carry Bit: How does it work?

Deutsch Most of us know from elementary school how to add multi-digit numbers on paper. Usage of the carry bit is the same concept, but not for base 10, not even for base 2, but for base 256 (in the old 8-bit-days), base 65536 (in the almost as old 16-bit-days), base 4294967296 (32 bit) or […]

Share Button