# Bit Manipulation Basics ## Decimal Number System * The decimal system, also known as the base-10 system, is the number system we use in our everyday lives. * It is called base-10 because a single digit can take 10 values from 0 to 9. The position of each digit in a decimal number represents a different power of 10. For example, ```cpp 342 = 300 + 40 + 2 = 3*10^2 + 4*10^1 + 2*10^0 ``` ```cpp 2563 = 2000 + 500 + 60 + 3 = 2*10^3 + 5*10^2 + 6*10^1 + 3*10^0 ``` --- ## Binary Number System * The binary system, also known as the base-2 system, is used in digital electronics and computing. * It has only two digits, which are 0 and 1. In the binary system, each digit represents a different power of 2. For example, ```cpp 110 = 1*2^2 + 1*2^1 + 0*2^0 = 4 + 2 + 0 = 6 ``` ```cpp 1011 = 1*2^3 + 0*2^2 1*2^1 + 1*2^0 = 8 + 0 + 2 + 1 = 11 ``` --- ### Binary to Decimal Conversion For this conversion, we need to multiply each digit of the binary number by the corresponding power of 2, and then add up the results. **Example 1:** Convert binary number 1101 to decimal number. ``` Starting from the rightmost digit, we have: 1 * 2^0 = 1 0 * 2^1 = 0 1 * 2^2 = 4 1 * 2^3 = 8 Adding up the results, we get: 1 + 0 + 4 + 8 = 13 Therefore, the decimal equivalent of the binary number 1101 is 13. ``` **Example 2:** Convert binary number 10101 to decimal number. - Starting from the rightmost digit, we have: ``` 1 * 2^0 = 1 0 * 2^1 = 0 1 * 2^2 = 4 0 * 2^3 = 0 1 * 2^4 = 16 ``` - Adding up the results, we get: ``` 1 + 0 + 4 + 0 + 16 = 21 ``` Therefore, the decimal equivalent of the binary number 10101 is 21. --- ### Question What is the decimal representation of this binary number: 1011010 **Choices** - [ ] 45 - [x] 90 - [ ] 94 - [ ] 130 **Explanation:** Starting from the rightmost digit, we have: 0 * 2^0 = 0 1 * 2^1 = 2 0 * 2^2 = 0 1 * 2^3 = 8 1 * 2^4 = 16 0 * 2^5 = 0 1 * 2^6 = 64 Adding up the results, we get: 0 + 2 + 0 + 8 + 16 + 0 + 64 = 90 Therefore, the decimal representation of the binary number 1011010 is 90. --- ### Decimal to Binary Conversion We can solve it using long division method, for which we need to repeatedly divide the decimal number by 2 and record the remainder until the quotient becomes 0. **Example:** Convert decimal number 20 to binary number. <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/034/146/original/bitmanipulationimage1.png?1683885852" width="40%" height="20%"> --- ### Question What is the binary representation of 45 ? **Choices** - [ ] 101100 - [ ] 101110 - [ ] 101111 - [x] 101101 **Explanation:** Here are the steps to convert decimal number 45 to binary: <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/034/147/original/bitmanipulationimage2.png?1683885879" width="40%" height="20%"> --- ### Addition of Decimal Numbers **Example -** ```cpp Calculate => (368 + 253) ``` <img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/033/817/original/Screenshot_2023-05-09_at_3.57.38_PM.png?1683628220" width="30%" > **Explanation:** * Start by adding the rightmost digits: 8 + 3 = 11 (digit = 11%10 = 1, carry 11/10 = 1) * Next column: 1 + 6 + 5 = 12 (digit = 12%10 = 2, carry 12/10 = 1) * Final column: 1 + 3 + 4 = 8 (digit = 8%10 = 8, carry 8/10 = 0) Therefore, answer is 821. --- ### Addition of Binary Numbers **Example 1:** | | 1 | 0 | 1 | 0 | 1 | |---|---|---|---|---|---| | + | | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 0 | 1 | 0 | **Explanation:** d = answer digit, c = carry * From right, 1 + 1 = 2 (d = 2%2=0, c = 2/2 = 1) * Next: 1 + 0 + 0 = 1 (d = 1%2=1, c = 1/2 = 0) * Next: 0 + 1 + 1 = 2 (d = 2%2=0, c = 2/2 = 1) * Next: 1 + 0 + 1= 2 (d = 2%2=0, c = 2/2 = 1) * Final: 1 + 1 = 2 (d = 2%2=0, c = 2/2 = 1) * Finally, 1 carry is remaining, so write 1. The result is 100010 in binary. **Example 2:** | | 1 | 1 | 0 | 1 | 0 | 1 | |---|---|---|---|---|---|---| | + | 1 | 0 | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 1 | 0 | 1 | 1 | **Explanation:** d = answer digit, c = carry * From Right: 1 + 0 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Next column: 0 + 0 + 1 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Next column: 0 + 1 + 1 = 2 (d: 2%2 = 0, c: 2/2 = 1) * Next column: 1 + 0 + 0 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Next column: 0 + 1 + 0 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Next column: 0 + 1 + 1 = 2 (d: 2%2 = 0, c: 2/2 = 1) * Finally, 1 carry is remaining, so write 1. The result is 1011011 in binary. --- ### Question What is the sum of these binary numbers: 10110 + 00111 **Choices** - [ ] 11111 - [ ] 10101 - [ ] 11011 - [x] 11101 **Explanation:** d = answer digit, c = carry * Start by adding the rightmost bits: 0 + 1 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Next column: 0 + 1 + 1 = 2 (d: 2%2 = 0, c: 2/2 = 1) * Next column: 1 + 1 + 1 = 3 (d: 3%2 = 1, c: 3/2 = 1) * Next column: 1 + 0 + 0 = 1 (d: 1%2 = 1, c: 1/2 = 0) * Final column: 0 + 1 + 0 = 1 (d: 1%2 = 1, c: 1/2 = 0) The result is 11101 in binary. --- ### Bitwise Operators * Bitwise operators are used to perform operations on individual bits of binary numbers. * They are often used in computer programming to manipulate binary data. * In bitwise operations, `0 -> false/unset` and `1 -> true/set` #### AND (&) * This operator takes two binary numbers and performs a logical AND operation on each pair of corresponding bits. * The resulting bit in the output is 1 if and only if both the corresponding bits in the input are 1. Otherwise, the resulting bit is 0. * The symbol for AND operator is '&'. ``` cpp 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1 ``` #### OR (|) * This operator takes two binary numbers and performs a logical OR operation on each pair of corresponding bits. * The resulting bit in the output is 1 if either one or both of the corresponding bits in the input are 1. Otherwise, the resulting bit is 0. * The symbol for OR operator is '|'. ``` cpp 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1 ``` #### XOR (^) * This operator takes two binary numbers and performs a logical XOR (exclusive OR) operation on each pair of corresponding bits. * The resulting bit in the output is 1 if the corresponding bits in the input are different. Otherwise, the resulting bit is 0. * The symbol for XOR operator is '^'. ``` cpp 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0 ``` #### NOT(!/~) * This operator takes a single binary number and performs a logical NOT operation on each bit. * The resulting bit in the output is the opposite of the corresponding bit in the input. * The symbols for NOT operator are '~' or '!'. ``` cpp ~0 = 1 ~1 = 0 ``` --- ### Bitwise Operations Example **Example 1:** ```cpp 5 & 6 //Binary representation 5 -> 101 6 -> 110 // Bitwise AND operation 101 & 110 = 100 = 4 ``` **Example 2:** ```cpp 20 & 45 //Binary representation 20 -> 010100 45 -> 101101 // Bitwise AND operation 010100 & 101101 = 111101 = 61 ``` **Example 3:** ```cpp 92 & 154 //Binary representation 92 -> 01011100 154 -> 10011010 // Bitwise OR operation 01011100 | 10011010 = 11011110 = 222 ``` **Example 4**: ```cpp ~01011100 //Binary representation 92 -> 01011100 // Bitwise NOT operation ~01011100 = 10100011 = 163 ``` **Example 5:** ```cpp 92 ^ 154 //Binary representation 92 -> 01011100 154 -> 10011010 // Bitwise XOR operation 01011100 ^ 10011010 = 11000110 = 198 ``` --- ### Question What is the value of A ^ B (i.e. A XOR B) where, A = 20 and B = 45? **Choices** - [ ] 4 - [ ] 20 - [x] 57 - [ ] 61 **Explanation:** * A = 20 = 00010100 (in binary) * B = 45 = 00101101 (in binary) Performing XOR on each pair of bits, we get: ``` 00010100 ^ 00101101 = 00111001 ``` Therefore, the value of A XOR B is 00111001, which is 57 in decimal format. --- ### Binary Representation of Negative numbers To convert a negative number to its binary representation, we can use two's complement representation. It works as follows - * Convert the absolute value of number to Binary representation. * Invert all the bits of number obtained in step 1. * Add 1 to the number obtained in step 2. Example of converting the negative number $-5$ to its $8-bit$ binary representation: 1. 5 to binary representation:```0000 0101``` 2. Invert all the bits:`0000 0101 -> 1111 1010` 3. Add 1 to the inverted binary representation: `1111 1010 + 0000 0001 = 1111 1011` **Note:** 1. The MSB has a negative base and that is where the negative sign comes from. 2. In case of positive number, MSB is always 0 and in case of negative number, MSB is 1. --- ### Question What is the binary representation of -3 in 8-bit signed integer format? Choose the correct answer **Choices** - [x] 11111101 - [ ] 01111101 - [ ] 00000011 - [ ] 10101010 --- ### Question What is the binary representation of -10 in 8-bit signed integer format? Choose the correct answer **Choices** - [x] 11110110 - [ ] 11110111 - [ ] 11111110 - [ ] 10101010 --- ### Range of Data Types What is the minimum & maximum no. that can be stored in the given no. of bits? ![](https://hackmd.io/_uploads/B1K61joE3.png) Generalisation for N Bits: ![](https://hackmd.io/_uploads/Hk1JbioE2.png) So, in general we can say that the {minimum,maximum} number in n-bit number is **{-2<sup>N-1</sup> , 2<sup>N-1</sup>-1}**. #### Integer(32-bit number) Integer is the 32 bit number. Its range is **{-2<sup>32-1</sup> , 2<sup>32-1</sup>-1}**. #### Long(64-bit number) Long is the 64 bit number. Its range is **{-2<sup>64-1</sup> , 2<sup>64-1</sup>-1}**. ### Approximation Approximation is done to better approximate the range of values that can be stored in integer or long. For integer, ![](https://hackmd.io/_uploads/SkjvJPtEn.png) For long, ![](https://hackmd.io/_uploads/rJjtkwY4n.png) --- ### Importance of Constraints Let's understand the importance of constraints using example. Suppose we have two integers as ``` a = 10^5 b = 10^6 ``` What will be the value of c ? #### TRY 1: ``` int c = a*b ``` It will Overflow, i.e **c** will contain wrong value. **Fails, the Reason:** * The calculation happens at ALU. * If we provide ALU with two INT, it calculates result in INT. * Therefore, $a*b$ will overflow before even getting stored in c. #### TRY 2: Say, we change the data type of c to long, what will be the value of c? ``` long c = a*b ``` **Fails, the Reason:** **c** would contain overflowed value since $a*b$ will overflow at the time of calculation, therefore there's no use to change datatype of **c** from INT to LONG. #### TRY 3: What if we typecast $a*b$ to long as below? ``` long c = long (a*b) ``` **Fails, the Reason:** Already overflown, hence no use to typecast later. #### TRY 4: What if we change the equation as shown below? ``` long c = (long) a * b ``` This is the correct way to store. **WORKS, the Reason:** * Here, we have typecasted **a** to long before multiplying with **b**. * If we send one INT and one LONG, ALU calculates answer in LONG. ### Question Given an array of size N, calculate the sum of array elements. **Constraints:** 1 <= N <= 10<sup>5</sup> 1 <= A[i] <= 10<sup>6</sup> Is the following code correct ? ``` int sum = 0; for (int i = 0; i < N; i++) { sum = sum + A[i]; } print(sum) ``` **We should look at constraints.** As per constraint, range of sum will be as follows - **1 <= sum <= 10<sup>11</sup>** The above code is incorrect since sum can be as big as 10<sup>11</sup> which can't be stored in INTEGER. Hence, we should change dataType of "sum" to LONG.