Bitwise Operators
C provides six bitwise operators, which operate on integer data
at the bit level. We'll discuss the two bitwise shift operators first, followed
by the four other bitwise operators (bitwise complement, bitwise and,
bitwise exclusive or. and bitwise inclusive or).
Bitwise Shift Operators
The
bitwise shift operators can transform the binary representation of an integer
by shifting its bits to the left or right. C provides two shift operators,
which are shown in below table
|
Symbol
|
Meaning
|
|
<<
|
left shift
|
|
>>
|
right shift
|
The
operands for << and >> may be of any integer type (including char).
The integer promotions are performed on both operands: the result has the type
of the left operand after promotion.
The
value of i << j is the result when the bits in i are shifted left by j
places. For each bit that is "shifted off' the left end of i, a zero bit
enters at the right. The value of i >> j is the result when i is shifted
right by j places. If i is of an unsigned type or if the value of i is
nonnegative, zeros are added at the left as needed. If i is a negative number,
the result is implementation-defined: some implementations add zeros at the
left end. while others preserve the sign bit by adding ones.
For
portability, it's best to perform shifts only on unsigned numbers.
The
Bitwise Complement
Bitwise operators in c# OR(|), XOR(^),
AND(&), NOT(~)
- binary OR(|) operator
- binary AND(&) operator
- XOR (^) operator
- Not (~) operator
Binary OR(|) operator
Quoting MSDN docs : Binary | operators are predefined for the integral types and bool. For integral types, | computes the bitwise OR of its operands. For bool operands, | computes the logical OR of its operands; that is, the result is false if and only if both its operands are false.
Lets focus on the integral types(types that can be represented as numbers) and how the computation takes place.
To understand the bitwise operator with clarity and how it computes the result, lets first construct a base 2 table from right to left incrementing the exponent by 1 for each power. So, since we have 8 bits in a byte, we make a table that lists 8 elements 128, 64, 32, 16, 8, 4, 2, 1.
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
Result
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
2
|
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
4
|
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
8
|
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
16
|
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
32
|
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
64
|
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
128
|
Ok, now that we have our binary 8bit table with digits to the power of 2^ up to 128, so for a simple 7 | 9, which yielded the result 15, lets look at how it was computed by first creating the binary representation using our base 2 table and then computing the binary | operation, so :
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
Calculation
|
Result
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
(4+2+1)
|
7
|
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
(8+1)
|
9
|
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
(8+4+2+1)
|
15
|
either bit or in both bits, otherwise it's 0. Not clear ? Lets try that again. How did we get the result 1111 ? It's a simple comparision. If either bit stacked ontop of one another are 1 or both are 1, then the result is 1, otherwise the result is 0. So 1 on 1 = 1, 1 on 0 = 1 but 0 on 0 = 0.
Binary AND(&)
operator
Binary & operators are predefined for the integral types and bool. For
integral types, & computes the logical bitwise AND of its operands. For
bool operands, & computes the logical AND of its operands; that is, the
result is true if and only if both its operands are true. So, lets quickly test this :
protected void Page_Load(object sender, EventArgs e)
{
byte a = 7;
byte b = 9;
int orComputed = a & b;
Response.Write(string.Format("
{0} & {1} Result :{2}", a, b, orComputed));
}
Output is :
7 & 9 Result :1
Lets convert to binary using our base 2 table, and dig deeper :
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
Calculation
|
Result
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
(4+2+1)
|
7
|
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
(8+1)
|
9
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
(1)
|
1
|
Binary Xor (^)
operator
Binary ^ operators are predefined for the integral types and bool. For
integral types, ^ computes the bitwise exclusive-OR of its operands. For bool
operands, ^ computes the logical exclusive-or of its operands; that is, the
result is true if and only if exactly one of its operands is true.A simple c# example :
protected void Page_Load(object sender, EventArgs e)
{
sbyte a = 7;
sbyte b = 9;
int orComputed = a^b;//on a negative
Response.Write(string.Format("
{0} ^ {1} Result :{2}", a,b, orComputed.ToString()));
}
output : 7 ^ 9 Result :14
Now, how did binary (^) Xor'ing 7 ^ 9 produce 14 ? This is because binary (^) is being performed on each pair of corresponding bits. If we have two matching zero's or one's, then the result is 0, otherwise 1. SO, 1 on 1 = 0, 0 on 0 = 0,
1 on 0 = 1, 0 on 1 = 1. Lets look at an example in our base 2 table of 7 and 9 in binary format :
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
Calculation
|
Result
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
(4+2+1)
|
7
|
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
(8+1)
|
9
|
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
(8+4+2)
|
14
|
Not (~) operator
The ~ operator performs a
bitwise complement operation on its operand, which has the effect of reversing
each bit. Bitwise complement operators are predefined for int, uint, long, and
ulong. This is also a unary operator so we don't need to pass a value. Unary operators perform an operation on a single operand eg. ~n and not x~y.
Binary (~) operator is the most confusing one. It performs reversing of each bit, so reversing a positive can produce a negative value. Negative Values Use Two's Complement format and is quite tricky.
A simple example :
protected void Page_Load(object sender, EventArgs e)
{
sbyte a = 7;
int orComputed1 = ~-a;//on a negative
int orComputed2 = ~a;// on a positive
Response.Write(string.Format("
~-{0} Result :{1}", a, orComputed1));
Response.Write(string.Format("
~+{0} Result :{1}", a, orComputed2));
}
output : ~-7 Result :6
~+7 Result :-8
As you can see, when the NOT(~) operator is applied to a positive number, the resulting value is a negative. This is because the value is reversed. Since this reversing yields a negative or positive depending on what value your reversing, use a signed type (a type that can store a negative value).
In the base table below, our binary number gets inverted. all 1's become 0 and 0 becomes 1.
A signed binary uses the left most bit to keep track of the sign(negative or positive).
In the c# compiler, negative values are represented internally in two's complement format. Two's complement can be obtained by negating each bit of the value, then adding 1. Performing two's complement twice generates the original value.
In the following base 2 table, one typical gotcha when inverting is to remember to start the inversion from the left of the first 1 value in our binary. So, say had we a binary representation of the digit 7(00000111), then we start inverting at the 2nd digit starting at the right, skipping the first(since it's 1) and get 11111001. A last thing to also note is how in our calculation we added a negative -1 to our result instead of a positive 1 -->> (-128+64+32+16+8+1)-1 ; While the two's complement format states that we need add 1, we are actually deducting 1 versus adding 1. This is because we have to consider 0 in the equation.
An easy method to get the two's complement of +7 :(left most is used to track sign, so add -1 to the result) :
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
Calculation
|
Result
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
(4+2+1)
|
7
|
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
(-128+64+32+16+8+1)-1
|
-8
|
Note the left most significant pair of corresponding bits in red. A value of 0 means positive and a value of 1 means negative and is used for tracking the sign in a signed binary.
One question still remains, why is the two's complement always a positive less(6) and a negative more(-8) ?
Why aren't we getting -7 for a 7 and vice versa. I guess the answer to this is simply "logic", we have to consider the 0.
How Bit-Fields Are Stored
Let's
take a close look at how a compiler processes the declaration of a structure
that has bit-field members. As we'll see, the C standard allows the compiler
considerable latitude in choosing how it stores bit-fields.
The rules
concerning how the compiler handles bit-fields depend on the notion of "storage
units." The size of a storage unit is implementation-defined: typical
values are 8 bits, 16 bits, and 32 bits. As it processes a structure
declaration, the compiler packs bit-fields one by one into a storage unit, with
no gaps between the fields, until there's not enough room for the next field.
At that point, some compilers skip to the beginning of the next storage unit,
while others split the bit-field across the storage units. (Which one occurs is
implementation-defined.) The order in which bit-fields are allocated (left to
right or right to left) is also implementation-defined.
C allows
us to omit the name of any bit-field. Unnamed bit-fields are useful as
"padding" to ensure that other bit fields are properly positioned.
Consider the time associated with a DOS file.
Defining
Machine-Dependent Types
Since the
char type—by definition—occupies one byte, we'll sometimes treat characters as
bytes, using them to store data that's not necessarily in character form. When
we do so, it's a good idea to define a BYTE type:
typedef unsigned char BYTE;
Depending
on the machine, we may want to define additional types. The x86 architecture
makes extensive use of 16-bit words, so the following definition would be
useful for that platform:
typedef
unsigned short WORD;
The
volatile Type Qualifier
On
some computers, certain memory locations are "volatile": the value
stored at such a location can change as a program is running, even though the
program itself isn't storing new values there. For example, some memory
locations might hold data coming directly from input devices.
The
volatile type qualifier allows us to inform the compiler if any of the data
used in a program is volatile, volatile typically appears in the declaration of
a pointer variable that will point to a volatile memory location:
volatile BYTE *p; /* p will point to
a volatile byte */
To
see why volatile is needed, suppose that p points to a memory location that
contains the most recent character typed at the user's keyboard. This location
is volatile: its value changes each time the user enters a character.
No comments:
Post a Comment