Bit Operations
From ASM Book
Bitwise operations
There are certain operations that you can use on individual bits or groups of bits. These operations are called bitwise operations and the operators we use to perform them are called bitwise operators.
There is a clear distinction between bitwise operators and bitwise instructions. Bitwise operators are symbolic operators that we shall use for clarifying operational concepts. Bitwise instructions are the equivalent machine instructions provided by the microprocessor to simulate these operators.
The logical bitwise instructions for 80386 and higher microprocessors are NOT, AND, OR, XOR, TEST, BSF, BSR, BT, BTC, BTS, BTR, and SETcc. These aid in manipulating bit values. Additional instructions, called the bit manipulation instructions, that aid in moving bits include SHL, SAL, SHR, SAR, SHLD, SHRD, ROL, ROR, RCL, and RCR. Since their uses are important to every programmer, a good grasp of the bitwise operations, operators, and their machine-equivalent instructions is essential to learning ASM.
WHY USE BITWISE OPERATORS
There are several reasons why we need to or should use bitwise operators. One of the most popular ones is: most programmers prefer using the individual bits of a variable as boolean options for their code rather than using separate boolean variables as shown in an example (not asm code) below. This saves memory space and speeds up the application program.
- Instead of using separate variables like this
bShowAmbientLight = TRUE bNoSound = FALSE bNoVideo = TRUE bNoSeek = TRUE . . .
We could create a variable
dwCodeOptions
- and assign options to its bits like this
bit 0 to bShowAmbientLight bit 1 to bNoSound bit 2 to bNoVideo bit 3 to bNoSeek and so on...
So, whenever bit 2 in dwCodeOptions is set to 1, the video preview will not be shown. If it were cleared to 0, then videos will be enabled. The same applies for the other options.
Setting, clearing, and toggling bits Setting a bit means changing its value to 1, while clearing a bit means changing its value to 0. By toggling a bit, we mean changing its current boolean value to the other boolean value. If it is currently 1, then toggling it will change it to 0. Knowing these terms is quite essential for understanding how to apply the operators discussed below.
Number of Options The number of bits you can use as boolean options in your code is limited by the size of the variable you use for storing them. If you create a 32-bit (DWORD-sized) variable, then 32 bits are available for use as boolean options. Creating a 16-bit (WORD-sized) variable will only allow for 16 bits to be used. Similarly, 8-bit (BYTE-sized) variables will restrict your options to 8 bits.
Bit Masks A bit mask is a temporary value that we use while setting, clearing, and toggling bits. As an example, see the one discussed under the AND Operator heading.
THE LOGICAL OPERATORS
NOT bitwise operator
NOT is probably the easiest bitwise operator to understand. The NOT operator is an unary operator, meaning that it takes only one operand. NOTing a value results in changing it to its opposite--NOT toggles values. If you NOT 1, you get 0. If you NOT 0, you get 1.
NOT(0) = 1 ; NOT changes "I am not going" to "I am going" NOT(1) = 0 ; NOT changes "I am going" to "I am not going" ; The parentheses only suggest that NOT is unary.
It should be noted, however, that NOT toggles the values of all the bits its operand contains. If you want to toggle the values of specific bits in an operand directly, you can use the XOR operator instead as discussed a little later.
Example:
NOT 1100 1011b ------------- = 0011 0100b NOT 0101 0111b ------------ = 1010 1000b
Assembly Syntax
MASM: NOT reg/mem HLA: NOT( reg/mem );
Use the NOT instruction to:
- Toggle all the bits in a value to get its 1's complement. To get the 2's complement use the NEG instruction or add 1 to the 1's complement.
Don't do this:
- NOT is not equal to NEG. NOT a = NEG a - 1 or NEG a = NOT a + 1. Never confuse the NOT instruction with the NEG instruction in assembly language. NOTing a value doesn't negate it but gives us the 1's complement (all bits flipped). The 2's complement notation is used to represent negative numbers by x86-based systems. The relationship between the two operations can be shown as below:
; => 2's complement = 1's complement + 1 NEG(0101 1100b) = NOT(0101 1100b) + 1
AND BITWISE OPERATOR
AND is quite simple to understand, in that when you AND a bit (one of two states) with another, if one of the bits is 0, the result would be zero. However if both bits are 1, the result would be 1.
"To result in TRUE, AND requires that BOTH of its operands be TRUE."
0 AND 0 = 0 ; If both Mary AND Julia are not going to the party, then I am not going too. 0 AND 1 = 0 ; If Mary is not ready to go AND Julia is, then I am not going. 1 AND 0 = 0 ; If Mary is ready to go AND Julia is not, then I am not going. 1 AND 1 = 1 ; If both Mary AND Julia are going, then I am also going.
Example:
0101 1110b
AND 1010 1010b
-------------
= 0000 1010b
1011 1110b
AND 0001 0101b
-------------
= 0001 0100b
Assembly Syntax
MASM: AND dest, src AND reg/mem, reg AND reg, reg/mem AND reg/mem, const HLA: AND( src, dest ); AND( reg, reg/mem ); AND( reg/mem, reg ); AND( const, reg/mem);
Use the AND operator to:
- Clear bits. ANDing a bit with 0, clears it. We use a temporary value called a bit mask for this purpose. Consider the conversion of lowercase letters to uppercase. The lowercase letters have binary representations wherein the 5th bit of any value is a 1. Each uppercase letter value has a 0 as its 5th bit. To convert 'a' (0110 0001b, 61h) to 'A' (0100 0001b, 41h), we use a bit mask with bit 5 as a 0 and the rest as 1s, so that it ANDs with the bit 5 (0) in 'a' to result in 'A'.
0110 0001b ; 'a'
AND 1101 1111b ; bit mask with bit 5 = 0
--------------
= 0100 0001 ; which is 'A'
OR bitwise operator
OR is somewhat the opposite of AND. When you OR a bit with another, if one of the bits is 1, the result will be 1. However if both are 0, the result would be 0.
"To result in TRUE, OR requires that ONE OR BOTH of its operands be TRUE."
0 OR 0 = 0 0 OR 1 = 1 1 OR 0 = 1 1 OR 1 = 1
Example:
11100101b 01010111b OR ------------ 11110111b 00000100b 10101010b OR ------------ 10101110b
Assembly Syntax
MASM: OR dest, src OR reg/mem, reg OR reg, reg/mem OR reg/mem, const HLA: OR( src, dest ); OR( reg, reg/mem ); OR( reg/mem, reg ); OR( const, reg/mem );
Use the OR instruction/operator to:
- Set a bit. ORing a bit with 1 will set it. You'll use this operator very much when programming Windows. For example, when setting options for Window styles you use the OR operator. For more information, see the Windows ASM volume.
- * Compare the value in a register to 0. Although, this is another little trick, it may prove useful and you may also see it used sometimes. It works because of the way the OR instruction affects the bits in the flags register. For example
; MASM OR eax, eax ; equivalent to cmp eax, 0 ; HLA OR( eax, eax );
is equivalent to eax comparing with 0 and sets the value of the Zero Flag bit in the flags register. You can then use a ZF-testing conditional jump (JNZ, JZ) to proceed with control flow. This instruction is equivalent to "cmp eax, 0", but since it produces shorter code, it is preferable to use it.
cmp eax, 0 ; compiles into 4 bytes - 66 83 F8 00 or eax, eax ; compiles into 3 bytes - 66 0B C0
XOR bitwise operator
XOR, or exclusive OR, is a binary operator like OR but with a slight difference. Frame what is said below, hang it on your favorite wall, and don't ever ask again.
"To result in TRUE, XOR requires that ONLY ONE of its two operands to be TRUE."
So, when you XOR two bits when both are valued 1, the result will ALWAYS be 0. XOR is used in some encryption technology such as XOR encryption (XOR encrpytion is weak) and for XOR swap. XOR allows you to swap the contents of two variables without using a third variable--only how we can do that is shown in actual code a little later.
0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0
- Example
0011 1000b
XOR 0011 1000b
-------------
= 0000 0000b
0101 0101b
XOR 1111 1000b
-------------
= 1010 1101b
</verbatim>
'''''Assembly Syntax'''''
<source lang="asm">
MASM:
XOR dest, src
XOR reg/mem, reg
XOR reg, reg/mem
XOR reg/mem, const
HLA:
XOR( src, dest );
XOR( reg, reg/mem );
XOR( reg/mem, reg );
XOR( const, reg/mem);
</source>
'''''Use the XOR instruction to:'''''
* ''Swap values.'' The x86 assembly XOR instruction allows us to swap two values without using a third placeholder. For example, to swap the values of the microprocessor registers eax and edx, you use the following XOR instructions.
<pre>
XOR eax, edx
XOR edx, eax
XOR eax, edx
Although this is a neat trick, the x86 already provides an XCHG instruction for swapping registers. This instruction is covered in the Data Transfer Instructions chapter.
Note also that the XOR instruction affects the x86 flags, whereas the XCHG instruction does not. The XCHG instruction, when you supply a memory operand, has an implicit LOCK associated with it, which slows the execution of the instruction by a tremendous amount. Using XOR is a possibility when you don't want a bus lock associated with the XCHG operation.
- Toggle bits in a value. To toggle all the bits in 1000 1011b (to 0111 0100b) you can use NOT or you can XOR the value with -1 (1111 1111b). XORing the operand with -1 does exactly what NOTing it does. To toggle specific bits, you use a bit mask wherein the toggling bits should be valued 1, while the others should be 0. For example, to toggle bit 5 and bit 3 in 1011 0101b, we use 0010 1000b as the bit mask.
; not code, only operator
1011 0101b
XOR 0010 1000b
---------------
= 1001 1101b
; code it like this
XOR 10110101b, 00101000b
- * Clear a register to 0. As interesting as it is, you can use the XOR operator to perform a very subtle operation that may not be very self-evident at first but is truly another marvel. XORing a register with itself will clear it to 0. Here's an example
XOR eax, eax ; same as "MOV eax, 0"
This instruction has the same effect as assigning 0 to the register. The above instruction has "MOV eax, 0" as its equivalent. However, "XOR eax, eax" is generally used (mostly to return 0 in conjunction with a RET directive). The reason it is used is that reg32 instructions are a little faster and much smaller.
- For example, "xor eax,eax" compiles as
66 33 C0
- while "mov eax,0" compiles as
66 B8 00 00 00 00
It occupies only 3 bytes as opposed to the 6 of the MOV version. The advantage to smaller instructions is that you can hold more in the instruction cache, speeding up program execution. Also, they require fewer memory fetches, which slow down programs as well.
- Detect errors and compute parity. Tricky XOR can "undo" itself. Exactly how it is done is explained a litte later, but first, let's answer: "What is parity?"
- Parity is " the state of being odd or even used as the basis of a method of detecting errors in binary-coded data " according to the Merriam-Webster Dictionary. Parity information is simply redundant information that is calculated from an actual set of values. Simply stated
- If you have N values stored, you use these values to calculate an extra value (parity information) so that the number of values stored now becomes N + 1. If you happen to lose ANY ONE of the N + 1 values, you can recalculate it using the remaining N.
Parity can be odd or even. Parity is calculated by first counting the number of 1s in a unit of binary data, and then adding a 0 or a 1 (parity value) to make the count odd or even. In even parity the total number of 1s (including the parity value) should be even. In odd parity, the total number of 1s (including the parity value) should be odd.
Example:
Consider the bits in 1001b:
1. 1001 has 2 1-bits.
2. We now add a parity bit to 1001.
a. If we want even parity, number of 1s (incl. parity bit) should be even.
So, the parity bit for 1001 in this case is 0, resulting in:
1001 0 ;--- parity bit = 0
b. If we want odd parity, number of 1s (incl. parity bit) should be odd.
So, the parity bit for 1001 in this case is 1, resulting in:
1001 1 ;--- parity bit = 1
Take another example, 1101b:
1. 1101 has 3 1-bits.
2. Add a parity bit:
a. For even parity,
1101 1 ;--- parity bit = 1
b. For odd parity,
1101 0 ;--- parity bit = 0
SHR bitwise operator
SHR means shift right. Taking a number as a binary, and when SHR n is performed on it, all the bits would move right by n times. The uses for shift right are that when you shift right a number by n, it is like dividing the number by 2^n. Dividing on a computer is much slower than using shifts. Thus, it is better to replace divides with shift rights.
Example:
01011010b SHR 3 = 00001011b 90 SHR 3 = 11 10101110b SHR 2 = 00101011b 174 SHR 2 = 43
Assembly Syntax
MASM: SHR dest, cnt SHR reg/mem, const SHR reg/mem, CL HLA: SHR( cnt, dest ); SHR( const, reg/mem ); SHR( CL, reg/mem );
SHL bitwise operator
SHL means shift left. Taking a number as a binary, and when SHL n is performed on it, all the bits in the number would move left by n times. The uses for shift left are that when you shift left a number by n, it is like multiplying the number by 2^n. Multiplication on a computer is much slower than using shifts. Thus, it is better to replace multiplication with shift lefts.
Example:
10010101b SHL 2 = 1001010100b 149 SHL 2 = 596 00011110b SHL 3 = 11110000b 30 SHL 3 = 240
Assembly Syntax
MASM: SHL dest, cnt SHL reg/mem, const SHL reg/mem, CL HLA: SHL( cnt, dest ); SHL( const, reg/mem ); SHL( CL, reg/mem );
