Bit Manipulation Flashcards
Base 10: 0- 9
Base 8: 0 - 7
Base 16: 0-9,a-f, 0,1,2,3….,8,9,a,b,c,d,e,f,0,1,…
Base 2: 0-1
Base 10 : decimal
Base 8: Octal
Base 16: Hexadecimal
Base 2: Binary
Positional Encoding
Each position represents some power of the base
562 = 5 x 100 + 6 x 10 + 2 x 1 = 5 x 10^2 + 6 x 10^1 + 2 x 10^0
Polynomial Representation of Numbers
Express each column/place as a_n x b^n
28_10 (means 28 base 10 or decimal)
Represent 28_10 as a polynomial in base 10 and base 2
2 x 10^1 + 8 x 10^0
Converting Bases: Algorithm1
Repreat until val==0:
determine largest power of R that is smaller than val
- let this be R^n to get quotient and remainder
- place quotient in the result location corresponding to R^n
- val = remainder
Convert 71_10 to base 3
3^4 = 81 so must use 3^3 = 27
71 - 54 = 17
2 x 3^3 + 1 x 3^2 = 63
17 - 9 = 8 2 x 3^3 + 1 x 3^2 + 2 x 3^1 = 69 8-6 = 2 2 x 3^3 + 1 x 3^2 + 2 x 3^1 + 2 x 3^0 = 71 2122_3
Converting Bases: Algorithm2
To convert from base 10 to base R
- Start with R^0 position (let n=0)
- repreat until val==0:
- divide val by R to produce a quotient and remainder
- - place remainder in the R^n position, val = quotient, n++
Convert 671_10 to base 3 with algorithm1
71/3 = 23 r 2
23/3 = 7 r 2
7/3 = 2 r 1
2/3 = 0 r 2
thus 2212_3
Converting between Binary and hex octal
1011100111
be careful in C int x = 033 ! = int x = 33
Just group the bits in groups of 4 and read from the right
[00]10 | 1110 | 0111
2 e 7
0 0 1 0 is 2 in decinmal, so 2 in hex is 2
1 1 1 0 is 14 in decimal, so 14 in hex is E (or e)
0 1 1 1 is 7 in decinmal, so 7 in hex is 7
For octal, group the bits in groups of 3 (starting from right) 1 | 011 | 100| 111 1 in decimal is 1 1 1 in decimal is 3 1 0 0 in decimal is 4 1 1 1 in decimal is 7 Thus octal is 1347
Convert from binary to decimal, octal, and hex
1 1 0 0 1 1 1 1
Decimal :
HEX: 1 1 0 0 | 1 1 1 1 = 12 | 15 = c | f
0xcf
Octal: 0 1 1 | 0 0 1 | 1 1 1 = 3 | 1 | 7
(null) 317
Decimal : 1 + 2 +4+ 8+ 64 + 128 = 207
Big Idea: Bits can represent ANYTHING
for Alphabet of 26 characters we use 2^5 = 32 more than enough to represent all alphabet. If we wanted to reperesent all cases (upper/lower) and punctuations we need 7 bits (ASCII)
Logical Value 0 =false 1=true
Colors: Red 00 , Green 01, Blue 11
Char is 1 byte
short is 2 byte
int is 4 byte
long is 8 byte
smallest biggest
unsigned char 0 255
char -128 127
unsigned short 0 65535
short -32768 32767
uint32_t (usually int). 0 2^(32) -1
int32_t (usually int). - 2^(31) - 1 2^(32) -1
How to addd two numbers in binary ?
14 + 11
same as decimal align and add , remember to carry
14 = 1 1 1 0
11 = 1 0 1 1
-> 1 1 0 0 1
How to subtract two numbers in binary ?
14 - 11
same as decimal align and subtract , remember to carry
14 = 1 1 1 0
11 = 1 0 1 1
-> 0 0 1 1
3
How to multiply?
5 x 3
In a sense its the same, or AND &
5 = 1 0 1
3 = 0 1 1
= 1 0 1 , then 1 0 1, then 0 0 0 , so we have (pad the right with a 0 each iteration)
1 0 1
1 0 1 0
0 0 0 0 0
= 0 1 1 1 1How to divide?
12 / 3
12 = 1 1 0 0 3 = 1 1
1 1 | 1 1 0 0 (long division)
get 1 0 0 which is 4 in binary
How to multiply and divide by powers of 2?
10, 20 ,40 , 5
10 = 1 0 1 0
if we wanted 20 just pad the right with 0
20 = 1 0 1 0 0
this works since now the highest value place is now 16 plus a 4
if we want 40 jsut pad another 0 to current value.
40 = 1 0 1 0 0 0
Thus idea is padding a 0 will double the value in decimal
to get 5 we remove so 10 removes from right. a 0
1 0 1 instead of 1 0 1 0
Fixed point (decimal value)
2^2. 2^1. 2^0. 2^-1. 2^-2. 2^-3 …..
10/4 = 2.5
10/4
10 = 1 0 1 0
4 = 1 0
Do longidivision and get 1 0 . 1
1 x 2^1 + 0 x 2^0 + 1 x2^-1 = 2 +1/2
10/8 in binary
is 1.25 or 1 . 0 1
Company that does music transportation
Giga Hertz
Waht do we want out of a number systm that inclues both positive and negative numbers
Symmetric
one / zero represntation
easy to detect + / -
easy to transition
How to represent negative numbers?
3-bit binary has a total of 8 values
Circular (see visual)
000 001 010 011 100 101 110 111
000 is consided positive 0
100 is considered negative zero but ignored
ANYTHING with a 1 infront is NEGATIVE
One’s Complement
000 & 111
111 & 000 are each others compliment thus represent similar things
1 0 1 is complemented by 0 1 0 which are -2 and 2
1 1 0 and 0 0 1 are complements and are -1 and 1
Two’s Complement
Flip all bits (&) and add a 1 to the right position
5 = 0 1 0 1 , then flip. 1 0 1 0 then 1 0 1 1
What is the binary number 0101 1110 1010 1100 in hexadecimal?
0x5eac
Binary Arithmetic
Addition: Unsigned , signed, fractions
Multiplying: Unsigned, signed, fractions
Foating point arithmetic
Adding signed numbers (easy): 6 + 7
1 1 0 (carry)
0 1 1 0 :6
\+ 0 1 1 1 :7
-----------
1 1 0 11 1 0 1 (carry) 0 1 1 0 :13 \+ 0 1 1 1 :5 ----------- 1 1 0 1
Adding unsigned numbers : -2 + 3
1 1 1 0 (carry) 1 1 1 0 : -2 \+ 0 0 1 1 : 3 ----------- 0 0 0 1 : 1
1 1 1 0 (carry) 1 0 1 1 : -5 \+ 0 0 1 1 : 3 ----------- 1 1 1 0 : -2
how to convert 5 to -5?
5 in binary is 0 1 0 1
-5 is the complement
0 1 0 1 to. 1 0 1 0
then add 1 to right 1 0 1 0 to 1 0 1 1
Adding signed fractions: 1/4 + 3/8
1 1 1 0 (carry)
1 1 1 0 : - 0.25
\+ 0 0 1 1 : 0.375
-------------
0 0 0 1
0 0 0 1 is 1/8 or 0.125
- 0.625 + 0.375
0 1 1 (carry)
1 0 1 1 : - 0.625
\+ 0 0 1 1 : 0.375
-------------
1 1 1 0
1 1 1 0 is -1/4 or -0.25
Prefixes help to identify the system (binary, hex, etc.)
what is prefix for hexadecimal?
What is prefix for binary?
Hexadecimal is 0x
Binary is 0b
Compare Binary value to decimal value
Binary Value Decimal Value
0 0
1 1
10 2
11 3
100 4
101 5
Binary Value Decimal Value
0 0
1 1
10 2
11 3
100 4
101 5
The position of each bit in the number determines how important that bit is to the numerical value of the number. Labeling the digits from right to left as d0, d1, d2, etc., each successive bit contributes a factor of two more than the next.
There’s no number you can represent in one system that you can’t represent in another.
PReference may sometimes be hexadecimal (16)
Binary bit sequences quickly grow to a large number of digits. Humans tend to have a tough time making sense of long sequences containing only 0’s and 1’s. While decimal is more compact, its base of 10 is a mismatch with binary’s base 2.
Decimal doesn’t easily capture the range that can be expressed using a fixed number of bits.
Why is hexadecimal used?
The large base allows each digit to represent enough information for hexadecimal numbers to be compact.
The position of each digit in the number determines how important that digit is to the numerical value of the number. Labeling the digits from right to left as d0, d1, d2, etc., each successive digit contributes a factor of sixteen more than the next.
Quiz 1 is due : Tuesday
Tuesday
Assignments cannot be submited late
NO, can not be submitted late
How many assignments can be dropped?
1
To get help , do not use autograder
do not use autograder
Looking at another student’s homework assignment violates AI
violation
Helping a fellow student debug their code violates AI
violation
Collaboration with other studnets on quizzes and assignments is not allowed
violation
given two hands with 3 fingers, you would be counting base:
7
convert to hexadecimal : 1100000011011110
1100 0000 1101 1110
0x. C 0 (zero) D. E
12
0
13
14
convert to binary. 0xcafdfb07
0x. cafdfb07
1100 1010 1111 1101 1111 1011 0000 0111
Convert to 6-bit 2's complement representation -16 13 -3 -10 26 -31
- 16: 110000
13: 001101 - 3: 111101
- 10: 110110
26: 011010 - 31: 100001
double check
3b)
- 48
-48
42/16 in unsigned decimal where decimal point is positioned in the middle
42/16 = 2 5/8 = 2.625
_ _ _ _ | _ _ _ _
0 0 1 0 for 2
1 0 1 0 for the .626 since the first 1 is 1/2 and third is 1/8
0 0 1 0 1 0 1 0
Do 8-bit 2’s complemnts representation on the following two binary-numbers
0 0 1 1 0 1 1 1
x 0 0 0 0 1 0 1 1
———————–
0 0 1 1 0 1 1 1 x 0 0 0 0 1 0 1 1 ----------------------- technically 0 0 1 1 0 1 1 1 x 1 0 1 1 -----------------------
0 0 1 1 0 1 1 1
0 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0
1 1 0 1 1 1 0 0 0
0 1 1 1 + 1 0 0 0
0 1 1 0 + 0 1 0 0
are 4-bit overflow
