Microsoft PowerPoint – 3_C_Part_2_Num_rep_Bit_operations
O
SU
C
SE
2
42
1
J.E.Jones
The C Language – Representing Data Logical vs Bitwise Operations; Bit Shifting;
Casting; Short-Circuit
Required Reading:
Computer Systems: A Programmer’s Perspective, 3rd Edition,
Chapter 2 thru Section 2.1.2
O
SU
C
SE
2
42
1
J. E. Jones
Have you ever thought about words that sound exactly
the same, but mean *very* different things depending
upon the language in which they were spoken?
https://www.daytranslations.com/blog/different-
meanings/
O
SU
C
SE
2
42
1
J. E. Jones
False friends
The words may be similar due to them coming from the same language family or due to loan words. In
some cases, they are ”false friends” meaning the words stand for something else from what you know.
• In English “to use the voice,” means to say something “aloud.” In Dutch, aloud means “ancient”
• The English word “angel” means a supernatural being often represented with wings. Angel in German
translates to ”fishing rod” and ”sting” in Dutch.
• You mean something not specific or whatever when you say “any.” But in Catalan, it is equivalent to
“year” although others use the word “curs.”
• The arm is an upper body extremity but for the Dutch it is the term used when they mean “bad.” But the
English term ”bad” is equivalent to ”bath” in Dutch.
• Bank could be an institution where people deposit their money, something or someone you trust or the
sloping land close to a body of water. For the Dutch, ”bank” means cough.
• An outlying building in a farm is called ”barn,” which is the term for ”children” in Dutch. On the other
hand, the English word ”bat” refers to a flying mammal or a club used to hit a ball. In Polish, the word
means, ”whip.”
• Beer in English means a ”bear” in Dutch, while they use the term ”big” to refer to a ”baby pig.”
• “Car in a motorized vehicle, but for the French, it means ”because.” A chariot for the English speakers is
a horse-drawn vehicle or a carriage, but the French use this term to mean something smaller, like a
”trolley.”
O
SU
C
SE
2
42
1
J. E. Jones
Now that we’ve had our cultural
moment for today, let’s talk about
how we represent data.
O
SU
C
SE
2
42
1
J. E. Jones
Modern computers store and process information as two-valued
signals.
– Bryant & O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd Edition
You can think of these two signals as off/on or true/false or 0/1, etc.
In isolation, a single bit is not very useful. When we group bits
together and apply some interpretation that gives meaning to the
different possible bit patterns, however, we can represent the
elements of any finite set.
– Bryant & O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd Edition
Note that this means a particular bit pattern could have several
different interpretations depending upon its context. Exactly like the
words we were looking at just a few moments ago..
O
SU
C
SE
2
42
1
J. E. Jones
Most of the time, binary (0s and 1s) data is represented
in blocks of 8 digits at a time since this is the smallest
addressable unit.
e.g., 1 byte=8 bits, 2 bytes=16 bits, etc.
For the next few slides and for other select times when
we want to discuss individual hexadecimal values, we
will be using binary data in blocks of 4 digits.
◦ When discussing 8 bits at a time, we call it a byte; when
discussing 4 bits at a time, it is called a nibble.
O
SU
C
SE
2
42
1
J. E. Jones
Same Bit Patterns
= Different Interpretations
= Different Meanings
O
SU
C
SE
2
42
1
J. E. Jones
DEC OCT HEX BINARY Symbol Description
48 060 0x30 00110000 0 Zero
49 061 0x31 00110001 1 One
50 062 0x32 00110010 2 Two
51 063 0x33 00110011 3 Three
52 064 0x34 00110100 4 Four
53 065 0x35 00110101 5 Five
54 066 0x36 00110110 6 Six
55 067 0x37 00110111 7 Seven
56 070 0x38 00111000 8 Eight
57 071 0x39 00111001 9 Nine
90 0132 0x5A 01011010 Z Uppercase Z
109 0155 0x6D 01101101 m Lowercase m
O
SU
C
SE
2
42
1
J. E. Jones
Binary to Decimal
Unsigned = simple binary = B2U
◦ All digits represent a positive power of 2
◦ NO NEGATIVE NUMBERS
◦ 0101 = 0*23+1*22+0*21+1*20 = 5
◦ 1111 = 1*23+1*22+1*21+1*20 = 15
◦ 1110 = 1*23+1*22+1*21+0*20 = 14
◦ 1001 = 1*23+0*22+0*21+1*20 = 9
We can represent any positive integer value we want
if we use enough bits.
◦ For some number of bits w, we can represent all
integer values between 0 and 2w-1.
◦ If w=4, then all integers between 0 and 15
◦ If w=10, then all integers between 0 and 1023
When we use the C language keyword unsigned, we
are saying to interpret bits in this manner.
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2U
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
O
SU
C
SE
2
42
1
J. E. Jones
Binary to Decimal
Signed = two’s complement = B2T
◦ Most significant digit (left-most bit) represents the
sign bit
◦ Remainder of digits represent positive powers of 2
◦ ANY POSITIVE NUMBER: SAME AS B2U
◦ 1111 = -1*23+1*22+1*21+1*20 = -8 + 7 = -1
◦ 1110 = -1*23+1*22+1*21+0*20 = -8 + 6 = -2
◦ 1001 = -1*23+0*22+0*21+1*20 = -8 + 1 = -7
◦ Another way, if sign bit = 1, then it’s a negative
number and to get the magnitude of that number,
invert all bits and add 1, then make sign negative
1010 changes to 0101+1 = 0110
0110 = 6, so final value is -6
We can represent any integer value we want if we use enough
bits.
◦ For some number of bits w, we can represent all integer
values between -2w-1 and 2w-1-1.
◦ If w=4, then all integers between -8 and 7
◦ If w=10, then all integers between -512 and 511
When we declare integer type variables in the C
programming language, this is the default way to interpret
bits.
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2T
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
O
SU
C
SE
2
42
1
J. E. Jones
Same number of bits w, just different interpretation.
Unsigned values
Signed values
0
0
2w-1
-2w-1 2w-1-1
O
SU
C
SE
2
42
1
J. E. Jones
Large binary numbers are cumbersome to read, so hexadecimal
digits offer a convenient way to represent binary data.
Each digit in a hexadecimal integer represents four binary bits.
Think of hexadecimal digits as a type of binary shorthand
It takes two hexadecimal digits together to represent a byte
A single hexadecimal digit represents a decimal value between
0 and 15, so letters A to F (lowercase also valid) represent
decimal values in the range 10 through 15. Since F is 15, then
consider them as unsigned values.
In hexadecimal, each digit position represents a power of 16.
0010 0110 1011 1111 = 0x26BF = 2*163+6*162+B*161+F*160
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
HEX
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
O
SU
C
SE
2
42
1
J. E. Jones
Just like those words we looked at a few moments
ago that changed meaning depending upon the
language we wished to use, these 4-bit binary chunks
can represent different values depending upon how
we choose to interpret them.
We can use hexadecimal values to represent 4 binary
bits. This typically makes them easier to read
Note that the binary value 1010 can represent:
Hexadecimal A (or hexadecimal a)
Decimal 10
Decimal -6
It depends upon how we wish to interpret those 4
bits.
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2U
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B2T
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
HEX
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
O
SU
C
SE
2
42
1
J. E. Jones
Suppose you are given the hexadecimal number :
0x173A
Convert to binary format by expanding each
hexadecimal digit, as follows:
◦ Hexadecimal 1 7 3 A
◦ Binary 0001 0111 0011 1010
This gives the binary representation:
◦ 0001011100111010 or 0001 0111 0011 1010
◦ Putting spaces between each nibble for readability in this class is acceptable (and,
sometimes, downright needful to keep your eyes from crossing).
O
SU
C
SE
2
42
1
J. E. Jones
Suppose you are given the binary number :
11110010101101
Starting from the right side, split the number into groups of 4 bits each (if the number of bits
is not a multiple of 4, the leftmost group will have fewer than 4 bits):
◦ Binary 11 1100 1010 1101
If the left-most group has fewer than 4 digits, add leading 0s if you wish the binary to
represent an unsigned number, then pattern match each nibble with the appropriate hex
digit.
◦ Binary 0011 1100 1010 1101
◦ Hexadecimal 3 C A D
This gives the hexadecimal representation:
0x3CAD
If the left-most group has fewer than 4 digits, add leading, 1s or 0s depending upon value
of MSB, if you wish the binary to represent a signed number, then pattern match each
nibble with the appropriate hex digit.
◦ Binary 1111 1100 1010 1101
◦ Hexadecimal F C A D
This gives the hexadecimal representation: 0xFCAD
O
SU
C
SE
2
42
1
J. E. Jones
•To convert from decimal to base b, divide the decimal
number by b, and write the remainders (which will be
between 0 and b – 1), until the quotient is zero.
•Then, write the remainders in order from the last
remainder obtained to the first remainder obtained.
•Example:
•convert (221)10 to base 2 (binary) (see the next slide)
O
SU
C
SE
2
42
1
J. E. Jones
Example: Convert (221)10 to binary
Quotient Remainder
2 221 1
2 110 0
2 55 1
2 27 1
2 13 1
2 6 0
2 3 1
2 1 1
0
Write the remainders in order from the last one obtained, to the first one obtained:
(221)10 = (11011101)2 = 0000 1101 1101
This expresses the binary representation of the original decimal number.
Why should we ultimately represent decimal 221 with a minimum of 12 binary digits?
We need at least 8 bits to represent 221, but, when looking at the value in 8 binary
digits, we really can’t tell whether we should be interpreting the value as unsigned or
signed since the most significant bit is 1, so we should used AT LEAST 9 digits.
Using a number of binary digits to represent a value that is a multiple of 4, makes it
easier to convert from binary to hex
O
SU
C
SE
2
42
1
J. E. Jones
Example: Convert (743)10 to hexadecimal
Hexadecimal is considered base 16.
Note: Since remainders can have values from 0 to base – 1, that is, 0 to 15 in this case,
we use F for 15, E for 14, D for 13, C for 12, B for 11, and A for 10
Quotient Remainder
16 743 7
16 46 E
16 2 2
0
Therefore, if we write the remainders in order from the last one obtained to the first one
obtained, we have:
(743)10 = (2E7)16 = 0x2E7
We only need 3 hexadecimal digits to represent 743 because the hexadecimal 2
interprets to 0010 in binary, so there is no confusion with respect to how the
value should be interpreted. If the most significant hexadecimal digit was 8 or
higher, then including a leading 0 hex digit would decrease confusion with
respect to the value the hex digits represent. Of course, adding a leading 0
(e.g.,0x02E7) doesn’t change its value and clearly defines a 16-bit value.
O
SU
C
SE
2
42
1
J. E. Jones
We can convert by multiplying the value of each digit,
dm, by dm, for m from 0 (least significant digit) to n-1
(most significant digit) for an n digit number, then
summing all the products obtained.
O
SU
C
SE
2
42
1
J. E. Jones
• Problem: Convert (5377)8 to decimal.
• Solution:
(5377)8 = 5 * 83 + 3 * 82 + 7 * 81 + 7 * 80
= 5 * 512 + 3 * 64 + 7 * 8 + 7 * 1
= 2,560 + 192 + 56 + 7
= 2,815
O
SU
C
SE
2
42
1
J. E. Jones
• Problem: Convert (5377)16 to decimal.
• Solution:
(5377)16 = 5 * 163 + 3 * 162 + 7 * 161 + 7 * 160
= 5 * 4096 + 3 * 256 + 7 * 16 + 7 * 1
= 20,480 + 768 + 112 + 7
= 21,367
O
SU
C
SE
2
42
1
J. E. Jones
Given 0x42, calculate
◦ Binary representation
◦ B2U
◦ B2T
Given 0x86, calculate
◦ Binary representation
◦ B2U
◦ B2T
O
SU
C
SE
2
42
1
J. E. Jones
Given 0x42, calculate
◦ Binary representation: 0b 0100 0010
◦ B2U: = 1 * 26 + 1 * 21 = 64 + 2 = 66
◦ B2T: = 1 * 26 + 1 * 21 = 64 + 2 = 66 (because msb 0)
Given 0x86, calculate
◦ Binary representation
◦ B2U
◦ B2T
O
SU
C
SE
2
42
1
J. E. Jones
Given 0x42, calculate
◦ Binary representation: 0b 0100 0010
◦ B2U: = 1 * 26 + 1 * 21 = 64 + 2 = 66
◦ B2T: = 1 * 26 + 1 * 21 = 64 + 2 = 66
(because msb = 0)
Given 0x86, calculate
◦ Binary representation: 0b 1000 0110
◦ B2U: = 1 * 27 + 1 * 22 + 1 * 21 = 128 + 4 + 2 = 134
◦ B2T: = -1 * 27 + 1 * 22 + 1 * 21 = -128 + 4 + 2 = -122
(because msb = 1)
O
SU
C
SE
2
42
1
J. E. Jones
Given 0x86, calculate
◦ Binary representation: 0b 1000 0110
◦ Alternate B2T: flip all bits: 0b 0111 1001
◦ add 1 : 0b 0111 1010
◦ Determine magnitude:
◦ 1 * 26 + 1 * 25 + 1 * 24 + 1 * 23 + 1 * 21 =
◦ 64 + 32 + 16 + 8 + 2 = 122
◦ Since we know value is negative, it represents -122
O
SU
C
SE
2
42
1
J. E. Jones
These few slides give the basics.
We’ll get a bit more involved in the 2nd half of the
semester
O
SU
C
SE
2
42
1
J. E. Jones
<< left-shift
>> right-shift
& bitwise AND
| bitwise OR
^ bitwise exclusive-OR
~ bitwise NOT (complement, not negation)
&& logical AND
|| logical OR Logical operators
! logical NOT
< less than
> greater than
<= less than or equal
>= greater than or equal
== equals
!= does not equal
Note 1: Bitwise operators evaluate same bit positions in two different operands. Like T/F tables in CSE 2321
Note 2: Logical operators evaluate an expression on each side of the operator, give that expression a value
of 1(true) or 0 (false), then perform the logical operation on the whole
Note 3: C has no keywords such as true or false, #defines are used
Note 4: OR, AND, and NOT: Behave differently between bitwise and logical operators.
BITWISE OPERATORS:
0 is 0
1 is 1
LOGICAL OPERATORS:
0 is FALSE
Everything else is TRUE
Practical Result:
0 if false;
1 if true
relational operators
Bitwise operators
O
SU
C
SE
2
42
1
J. E. Jones
Does this remind anyone of Foundations I? It should.
int a = 10;
int c = 0;
int a = 10;
int c = 1;
int a = 10;
int c = 3;
a & c
Bitwise (each
column of bits
is individually
combined)
a=10=1010b
c= 0=0000b
—————-
0000b
010
a=10=1010b
c= 1=0001b
—————-
0000b
010
a=10=1010b
c= 3=0011b
—————-
0010b
210
a && c
Logical (value
expression is
combined)
a=True
c=False
———–
False
a=True
c=True
———–
True
a=True
c=True
———–
True
O
SU
C
SE
2
42
1
J. E. Jones
.
int a = 10;
int c = 0;
int a = 10;
int c = 1;
int a = 10;
int c = 3;
a | c
Bitwise (each
column of bits
is individually
combined)
a=10=1010b
c= 0=0000b
—————-
1010b
1010
a=10=1010b
c= 1=0001b
—————-
1011b
1110
a=10=1010b
c= 3=0011b
—————-
1011b
1110
a || c
Logical (value
of expression is
combined)
a=True
c=False
———–
True
a=True
c=True
———–
True
a=True
c=True
———–
True
O
SU
C
SE
2
42
1
J. E. Jones
int a = 10;
int c = 0;
int a = 10;
int c = 1;
int a = 10;
int c = 3;
a ^ c
Bitwise (each
column of bits
is individually
combined)
a=10=1010b
c= 0=0000b
—————-
1010b
1010
a=10=1010b
c= 1=0001b
—————-
1011b
1110
a=10=1010b
c= 3=0011b
—————-
1001b
910
The C Programming Language does not define a logical exclusive OR
O
SU
C
SE
2
42
1
J. E. Jones
int a = 10;
~a
Bitwise (each column of bits is
individually changed)
a=10=1010b
—————-
0101b
610
!a
Logical (value of expression is
combined)
a=True
———–
False
O
SU
C
SE
2
42
1
J. E. Jones
When we represent values in binary, we can do what is
called “shifting” bits either to the right or to the left.
Left shift example:
◦ Binary value: 0111 0101
◦ Left shift 2 places: 1101 0100 (fill with 0’s)
Bit
Bucket
01
The Bit Bucket is a fictitious, but often
used item
O
SU
C
SE
2
42
1
J. E. Jones
Shifting to the right has 2 options:
◦ Arithmetic shift – typically used when interpreting as signed values
◦ Logical shift – typically used when interpreting as unsigned values
Shift Right Arithmetic
◦ Fills in from the left with copy of Most Significant Bit
◦ Preserves the sign of the value
◦ Used when interpreting the value as B2T
◦ Binary value: 1111 0101
Shift Right Arithmetic 1 bit: 1111 1010
Shift Right Arithmetic 2 bits: 1111 1101
◦ If the MSB had been 0, then new
bits would be 0s
Shift Right Logical
◦ Fills in from the left with 0’s
◦ Used when interpreting the binary value as B2U
◦ Binary value: 1111 0101
Shift Right Logical 1 bit: 0111 1010
Shift Right Logical 2 bits: 0011 1101
Bit
Bucket
1 01
01
1
The Bit Bucket is a fictitious, but
often used item
O
SU
C
SE
2
42
1
J. E. Jones
Used to compare two values
◦ < <= > >= (Higher precedence than == and !=)
◦ == !=
Precedence order is given above, L-R associativity
Arithmetic operators have higher precedence than relational
operators
An expression that is TRUE evaluates to a nonzero number
(generally 1). A FALSE expression evaluates to zero.
◦ For example, the expression (0 == 2) evaluates to 0.
◦ while the expression (2 == 2) evaluates to a 1
(non-zero technically, but usually 1).
O
SU
C
SE
2
42
1
J. E. Jones
ANSI C does not have a distinct Boolean type
◦ int is used instead (usually, but other types are possible)
0 is treated as FALSE
Non-zero is treated as TRUE
i = 0;
while (i – 10) {
…
i = i + 1;
}
◦ As long as (i-10) 0, it is considered TRUE, and the body of
the while loop will execute.
(Later versions of C have Boolean type)
O
SU
C
SE
2
42
1
J. E. Jones
ANSI C does not have a distinct Boolean type
◦ int is used instead (usually, but other types are possible)
0 is treated as FALSE
Non-zero is treated as TRUE
i = 0;
while (i – 10) {
…
i = i + 3; /* what happens here? */
}
◦ As long as (i-10) 0, it is considered TRUE, and the body of
the while loop will execute.
(Later versions of C have Boolean type)
O
SU
C
SE
2
42
1
J. E. Jones
Short-Circuit Evaluation: Relational statements stop
evaluating once a statement’s value is definitive
◦ In (x && y), if 1st condition evaluates to false (e.g., if expression
x==0), evaluation stops
◦ It does not matter what the outcome of the y expression is because (x
&& y) will always evaluate to false. y is not evaluated or compared
(i.e., instructions in y expression are not executed)
◦ Same for OR if first expression evaluates to 1 (TRUE).
This can cause buggy code (or not!)
◦ This is a valid way to write code
◦ There are many arguments made that it can be a correct and expedient
way to write some code
◦ Be very cautious
O
SU
C
SE
2
42
1
J. E. Jones
Short-Circuit Evaluation:
func1(float a, float b){
if ((b != 0.0f) && (a/b < 0.5f)){
printf(“ The result of func1 is %f.4\n”, ((a*b) + (a/b)));
}
else {
printf(“ The result of func1 is undefined.\n”);
}
return;
}
In this example, short-circuit evaluation saves your bacon!
Without short-circuit, this code will seg fault when b=0.0f and a/b is computed.
NOTE: (b !=0.0f) and (a/b< 0.5f) are logical expressions and have values of
TRUE or FALSE.
O
SU
C
SE
2
42
1
J. E. Jones
Short-Circuit Evaluation:
func1(int a, int b){
int func_result = 1;
if ((b == 0) && ((func_result = (++a*b+3)))){
printf(“ The result of func1 is %d\n”, a*func_result);
}
return;
In this example, short-circuit evaluation might cause you problems because the
variable a and func_result sometimes change value in the 2nd expression.
NOTE: (b==0) and ((func_result = (++a*b+))) are logical expressions and
have values of TRUE or FALSE.
O
SU
C
SE
2
42
1
J. E. Jones
• Type casting – EXPLICIT
• You purposely convert a variable from one data type to another data type in
your code
• Syntax: (type-name) variable
• Type combination and promotion - IMPLICIT type casting
• (‘a’ – 32) = 97 – 32 = 65 (if used as a char = ‘a’)
• Smaller type (char) is “promoted” to be the same size as the larger type (int),
remember that constants default to int.
• Determined at compile time – type of the whole expression is based purely
on the types of the values in the expressions
• Does not lose information – convert from type to compatible larger type
• Whether the casting is implicit or explicit, the compiler will create
separate storage for the cast value, and any operands that are
necessary to determine it. [See next slide for example]
32
O
SU
C
SE
2
42
1
J. E. Jones
The usual arithmetic conversions are
implicitly performed to cast values of
distinct types to a common type.
-Compiler first performs integer promotion
(promotion of char to int)
-short data type is ignored
-If operands still have different types, then
any variables or constants in operand
expressions are converted to the type that
appears highest in the following hierarchy
(except any variables that were already of
that type; for those, no conversion is
necessary)
O
SU
C
SE
2
42
1
J. E. Jones
The following code is supposed to scale a homework score in
the range 0-20 to be in the range 0-100.
cnvt_score(){
int score;
/* score gets set in the range 0<=score <=20 */
score = (score / 20) * 100; /*convert to
percentage*/
return(score);
}
Does this work?
O
SU
C
SE
2
42
1
J. E. Jones
This does not work! Unfortunately, score will almost always be set to 0
for this code because the integer division in the expression (score/20)
will be 0 for every value of score less than 20.
• The fix is to force the quotient to be computed as a floating-point
number even though it will truncate to an int when assigned to score
score = ((double)score / 20) * 100; /*OK – double floating-point
division with explicit cast */
score = (score / 20.0) * 100; /*OK – double floating-point division
with implicit casting because float (double) constant 20.0 */
score = (int)(score / 20.0) * 100; /*NO -- the (int)cast truncates the
floating quotient back to 0 if score < 20 prior to multiplication */
35