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, 32, 64,… Bit: How many Bits are affected by the operation?
- Shift vs. Rotate: Shift moves bits to the left or right, filling in 0 or 1 in the positions that get freed by this. The bits that get shifted out usually go to the carry bit, so the last one of these wins, if the shift is done by more than one bit. Rotation means what some English knowledge suggests: The bits shifted out are moved in on the other side.
- ROL and ROR vs RCL and RCR: Rotation through Carry (RCL or RCR) means that the carry bit participates as bit 9., 17., 33. or 65. ROL and ROR leave the carry bit alone, at least do not use it as input.
- Logical vs. Arithmetic Shift: This deals with the „sign“. For arithmetic Shift the number is considered to be signed in two’s complement. Therefore right shift does not necessarily introduce a 0 as new most significant bit, but depending on the sign introduces a 0 or a 1.
Current CPUs have barrel shifts or something like that built into the hardware, so shift and rotate operations by more than one bit position are much faster than sequences of single shifts. This technology has been around on better CPUs for decades and is not at all new.
How the commands are called exactly and possibly some details about there operations depend on the CPU architecture.
Examples (8 bit) for shifting and rotating by one bit position:
| Vorher (Carrybit in Klammern) | ROL (rotate left) | RCL (rotate left through carry) | ROR (rotate right) | RCR (rotate right through carry) | ASL / SHL (arithmetic/logical shift left) | SHR (logical shift right) | ASR (arithmetic shift right) |
|---|---|---|---|---|---|---|---|
| 00000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) |
| 00000000 (1) | 00000000 (1) | 00000001 (0) | 00000000 (1) | 10000000 (0) | 00000000 (0) | 00000000 (0) | 00000000 (0) |
| 00000001 (0) | 00000010 (0) | 00000010 (0) | 10000000 (0) | 00000000 (1) | 00000010 (0) | 00000000 (1) | 00000000 (1) |
| 00000001 (1) | 00000010 (1) | 00000011 (0) | 10000000 (1) | 10000000 (1) | 00000010 (0) | 00000000 (1) | 00000000 (1) |
| 10000000 (0) | 00000001 (0) | 00000000 (1) | 01000000 (0) | 01000000 (0) | 00000000 (1) | 01000000 (0) | 11000000 (0) |
| 10000000 (1) | 00000001 (1) | 00000001 (1) | 00000001 (1) | 11000000 (0) | 00000000 (1) | 01000000 (0) | 11000000 (0) |
| 11111111 (0) | 11111111 (0) | 11111110 (1) | 11111111 (0) | 01111111 (1) | 11111110 (1) | 01111111 (1) | 11111111 (1) |
| 11111111 (1) | 11111111 (1) | 11111111 (1) | 11111111 (1) | 11111111 (1) | 11111110 (1) | 01111111 (1) | 11111111 (1) |
These shift and rotate operations are needed to express multiplications by powers of two and division by powers of two. In C, C++, C#, Perl, Java and some other porgramming languages these operations are included and written as „<<" (for ASL or SHL), ">>“ (for SHR) and „>>>“ for ASR.
Links
- Carry Bit: How does it work
- How to recover the Carry Bit
- Carry Bit, Overflow Bit and Signed Integers
- Deutsch (this article in German)
- Bit Shifts (Wikipedia)
- Logical Shift (Wikipedia)
- Bitwise Operators (Python-Wiki)
- LLVM ‘shl’ Instruction
Schreibe einen Kommentar