KoblentsBlog Photography
Contact About
Ches
Intro. to Bitwise Operators
This article will deal with an introduction to bitwise operators, written in the way that most makes sense to me, from a hardware and low-level software point of view. The basics apply to anyone, though those working in higher-level languages may only care about how to use them and nothing more in depth.
There are a lot of bitwise operators. They are important in programming and represent essentially all combinational digital logic. Bitwise operators operate on the individual bits of a variable. For example, where you see the number 20 (stored as an unsigned byte), a bitwise operator sees 0x14 or 0b00010100. It doesn't care about the integer 20; it cares about the sequence of bits.
	AND operator: 1 if both bits are 1, 0 otherwise
	A | B | A AND B
	0 | 0 | 0
	0 | 1 | 0
	1 | 0 | 0
	1 | 1 | 1

	AND usage:
	Let A = 5		A = 0b101
Let B = 3 B = 0b011
A AND B 101 AND 011 --- RESULT 001 A & B == 0b001 == 1 base 10
Hopefully this made sense - each bit column is ANDed irrespective of other columns. Now, let's list the most common operators:
	A AND B:	1 if both bits 1
	A OR B:		1 if at least one bit 1
	A XOR B:	1 if exactly one bit 1
	NOT A:		1 if bit is 0
Common notation in most programming languages (from low- to high-level ones):
	A AND B:	A & B
	A OR B:		A | B
	A XOR B:	A ^ B		(note: xor means exclusive OR)
	NOT A:		~A
This should not be confused with boolean operators. They are very similar, but deal with the entire variable as a whole, instead of each bit. Common notations in most languages:
	A AND B:	A && B
	A OR B:		A || B
	NOT A:		!A
The difference is that a bitwise operator will return a value of the same type - for example, the bitwise OR of two ints will be an int - whereas a boolean operator returns a boolean value. Observe:
	0b011	&	0b110	=	0b010	(bitwise AND of 3 and 6 is 2)
	0b011	|	0b110	=	0b111	(bitwise OR  of 3 and 6 is 7)
	0b011	^	0b110	=	0b101	(bitwise XOR of 3 and 6 is 5)
		~	0b011	=	0b100	(bitwise NOT of 3       is 4)
	Compared to
	0b011	&&	0b110	=	TRUE	(both values non-zero)
	0b011	||	0b110	=	TRUE	(at least one value is non-zero)
		!	0b011	=	FALSE	(NOT of non-zero is zero, is FALSE)
As you can see, AND, OR, XOR take two operators, but NOT takes just one. AND, OR, XOR can be extended to take more than two operators. Depending on the implementation, this is either decomposed into multiple operations, or executed as one operation. The choice of decomposition or executing at once is made on various levels - for example, decomposition can happen at interpretation, compilation, decode from macro-operation to micro-operation, inside the actual ALU, or even on the gate or transistor level. Consider the following case:
	AND: result 1 if all inputs 1
	A | B | C | A & B & C
	0 | 0 | 0 | 0
	0 | 0 | 1 | 0
	0 | 1 | 0 | 0
	0 | 1 | 1 | 0
	1 | 0 | 0 | 0
	1 | 0 | 1 | 0
	1 | 1 | 0 | 0
	1 | 1 | 1 | 1
	Decomposition:
	A & B & C == (A & B) & C, or A & (B & C), which are equivalent

	--------------------------------------------------------------

	Interpeted language:
		dest = A & B & C
	Decomposition: code executed by interpreter
		temp1 = A & B
		dest = temp1 & C

	--------------------------------------------------------------

	Compiled language:
		dest = A & B & C
	Decomposition: assembly - or equivalent hex
					; assume values loaded into r8, r9, r10
					; assume dest will be r8
		and	r8, r9		; r8 = r8 & r9 = (A) & (B)
		and	r8, r10		; r8 = r8 & r10 = (A & B) & C

	--------------------------------------------------------------

	Assembly language:
		and	r8, r9, r10	; r8 = r8 & r9 & r10
	Decomposition: micro-operations, or uops
		uop_and	r8, r9		; r8 = r8 & r9
		uop_and	r8, r10		; r8 = r8 & r10

	--------------------------------------------------------------

	Micro-operation:
		uop_and	r8, r9, r10
	Decomposition: physical hardware
		

	--------------------------------------------------------------

	Gate level:
		
	Decomposition: transistor level hardware
		
Decompositions in notation common to most programming languages:
	A & B & C	(A & B) & C == A & (B & C)	1 if all bits 1
	A | B | C	(A | B) | C == A | (B | C)	1 if at least one bit 1
	A ^ B ^ C	(A ^ B) ^ C == A ^ (B ^ C)	1 if odd number of bits 1
Those are the most-used bitwise operators. Here are some that complement the ones we've seen:
	NAND		inverse of AND
			1 if NOT (all bits 1)
			1 if at least 1 bit 0
	NOR		inverse or OF
			1 if NOT (at least 1 bit 1)
			1 if all bits 0
	XNOR		inverse of XOR
			1 if NOT (odd number of bits 1)
			1 if even number of bits 1
And the last bitwise operators deal with shifting (arithmetic versus logical bit shift not covered here):
	Let A = 0b0011

	SHL: Shift Left (all bits shifted left)
	A << 1			A << 2
	A == 0b0110		A == 0b1100

	SHR: Shift Right (all bits shifted right)
	A >> 1			A >> 2
	A == 0b0001		A == 0b0000
This leads us into the next topic: Dangers of bitwise shifting!
Ches Koblents
September 9, 2013
 
« Newer Older »
© Copyright Koblents.com, 2012-2017