Applying C - Basic Arithmetic As Bit Operations |

Written by Harry Fairhead | |||

Monday, 21 December 2020 | |||

Binary arithmetic used to be well understood because you needed to know how the hardware worked - it is still important to understand it. This extract is from my book on using C in an IoT context. ## Now available as a paperback or ebook from Amazon.
- C,IoT, POSIX & LINUX
- Kernel Mode, User Mode & Syscall
- Execution, Permissions & Systemd
Extract Running Programs With Systemd - Signals & Exceptions
Extract Signals - Integer Arithmetic
Extract: Basic Arithmetic As Bit Operations - Fixed Point
Extract: Simple Fixed Point Arithmetic - Floating Point
- File Descriptors
Extract: Simple File Descriptors Extract: Pipes ***NEW - The Pseudo-File System
Extract: The Pseudo File System - Graphics
Extract: framebuffer - Sockets
- Threading
Extract: Condition Variables Extract: Deadline Scheduling - Cores Atomics & Memory Management
- Interupts & Polling
- Assembler
Extract: Assembler
Also see the companion book: Fundamental C <ASIN:1871962609> <ASIN:1871962463> <ASIN:1871962617> <ASIN:1871962455> Arithmetic is the forgotten task. We just expect machines to evaluate whatever expression we write and we expect it to get it right – or right enough not to cause a problem. Part of the reason for this unreasonable assumption is the availability and success of floating point arithmetic. However, even floating point arithmetic can give you results that are closer to random numbers than a valid answer if you don’t take care. This chapter isn’t about floating point arithmetic – for that see Chapter 7. Smaller computers often don’t have a hardware floating point unit and if you want to use floating point you have to use a software implementation which is slow. In most cases a better option is to use integer or fixed-point arithmetic which is more appropriate for embedded processors and special digital signal processors, for example. In this chapter we look at the basics of integer arithmetic and the next tackles its extension to fixed-point arithmetic. It is assumed that you know the basics of binary numbers, the bitwise operators and how to use hexadecimal. If you are in any doubt about these topics see: ## Binary Integer Addition as Bit ManipulationComputer arithmetic is almost universally done in binary. It hasn't always been this way and even today decimal representations are sometimes important, see the next section on Binary Coded Decimal, BCD. Binary integer addition is something we generally take for granted – the hardware just does it, but it can be implemented using bitwise logic and shifts, and it is instructive to do so. Addition of two bits generates a Result bit and a Carry bit:
You can see that the result is an XOR and the carry is simply an AND. This is called a half adder because it doesn’t deal with the problem of taking account of anything that might have been generated by an earlier pair of bits being added.
Can we do the same job in C without using the add operator? ## Addition As Bit ManipulationA half adder is easy as it is just two logical operations. If a and b are ints then: r=a^b; is the set of result bits and: c=a&b; is the set of carry bits when a and b are “half added”. For example, for a=0101 and b=0111: r= 0101 ^ 0111 = 0010 and: c= 0101 & 0111 = 0101 If you do the addition you will see that these are the result and carry bits of half adding each pair of bits without worrying about any earlier carry bits. Each of the carry bits has to be added to the result but to the next higher-order bit. In other words, we need to add the carry to the result shifted one bit to the left: a+b=r+c<<1 or: a+b= a^b + a&b<<1 This is the fundamental formula for addition but notice that it doesn’t get rid of the addition operator! To do this we have to write it in terms of the logical operators. That is, to add the result and the shifted carry we have to use: r1=r^(c<<1); c1=r & c; You can now see what the problem is – there might be another carry bit in c1 that has to be added to the result. The fact of the matter is that addition is an iteration of two logical operations and a shift, and this fact is hidden from us by its implementation in hardware. In hardware, the carry bits propagate through the full adder and it is the propagation time that is the hardware’s equivalent of the iteration. So, to compute an addition, a+b, without using the addition operator, we need to use: int ans = a; int c = b; int temp=0; while (c > 0) { temp = (ans^c); c = (ans & c) << 1; ans=temp; } The loop ends when there is no carry and if the most significant bit of the carry is set at any point then an overflow has occurred. It is worth noting that the term overflow is perhaps not the correct one. The C90 standard states that integer addition cannot overflow, it simply rolls over. That is, if a is the maximum value that can be represented, a+1 is 0. This is the wrong answer, but it isn’t necessarily an error, as we shall see. ## In chapter but not in this extract:- Decimal Arithmetic with BCD
- BCD Arithmetic
- Negative Numbers
- Overflow and Undefined Behavior
- GCC Overflow Detection
- DIY Overflow Detection Before it Happens
- Using Unsigned Arithmetic to Detect Overflow
- Avoiding Overflow by Increased Precision
- Trapping Signed Overflow
- Detecting Unsigned Rollover
- Modular Arithmetic
- Division by Zero
- Trapping Division by Zero
## Summary-
Integer arithmetic is achieved using a full adder. When implemented in software, integer addition is iterative. -
*Binary is not the only possible representation - Binary Coded Decimal is also common.* -
*Implementing BCD arithmetic is surprising difficult to do efficiently.* -
*There are different ways of representing negative numbers. Sign magnitude is common, but two’s-complement is preferable as it takes care of the sign automatically.* -
*What happens when arithmetic results in a value that cannot be represented is a difficult topic. For unsigned arithmetic the standard defines that it should result in a rollover. For signed arithmetic overflow is undefined behavior.* -
*Detecting overflow before it happens is an important task and there are many ways of doing the job. There are built-in functions in GCC, but if you don’t want to, or can’t, use them it is possible to test for overflow using conditionals.* -
*To avoid problems with undefined behavior, you can always implement signed arithmetic using unsigned operators, or you can increase the precision so that overflow cannot occur.* -
*In many cases the operating system will provide a software interrupt, or trap, that you can use to detect and handle signed overflow. In most cases you will also need to use some advanced C to implement a try-catch construct.* -
*Although most of the problems are centered on signed overflow, it can be important to detect unsigned overflow.* -
*Modular arithmetic is, in fact, what all integer arithmetic is. Integer division and the mod or remainder operator are very useful in general programming.* -
*Detecting division by zero should be easy, but it is often difficult to detect it in a way that allows you to handle it in software.*
## Related ArticlesRemote C/C++ Development With NetBeans Getting Started With C/C++ On The Micro:bit To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |
|||

Last Updated ( Monday, 21 December 2020 ) |