Scribd
Upload
9 views59 pages

A2SV G5 - Bitwise Operation - With Code-Merged

Uploaded by

kebedeadugna45

bitwise

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt

A2SV G5 - Bitwise Operation - With Code-Merged

Uploaded by

kebedeadugna45
9 views59 pages
bitwise

Original Title

A2SV G5 - Bitwise Operation - With code-merged

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

bitwise

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
9 views59 pages

A2SV G5 - Bitwise Operation - With Code-Merged

Uploaded by

kebedeadugna45
bitwise

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 59

Bitwise

Operations 0 1
Lecture Flow
● Pre-requisites
● De nition of Bits
● Bit representation of integers
● Bitwise operators
● Bitwise operators properties
● Bit Masking
● Bit Masking operations
● Python’s built in functions
● Practice questions
● Quote of the day

2
Pre-requisites

No prerequisites folks

3
What are Bits?
Bit is the smallest unit of data in a computer system and
represents a binary digit, which can have one of two values:
0 or 1.
Bit Representation for unsigned?
Bit Representation
Bit Representation for signed?
Bit Representation
2’s Complement
2’s Complement
● A method to represent negative numbers
● Most popular method
● Allows adding negative numbers with the same logic gates as positive
numbers
● Main Idea: x + (-x) = 0
2’s Complement
How to convert number to 2's complement
1. Convert the positive number to binary
2. Flip the bits (1 to 0 and 0 to 1)
3. Add 1
Why Bits?
● Some questions require bit manipulations.
● It can be used to optimize solutions and simplify solutions.
Bit Operators
Bit Operators
● NOT (~)
● AND (&)
● OR (|)
● XOR (^)
● Bit Shifts (<<,>>)
NOT
AND
Check yourself

3&2=?
OR
Check yourself

7|8=?
XOR
Check yourself

4^9=?
Left Shift
Check yourself

1 << 3 = ?
Right Shift
Check yourself

16 >> 3 = ?

● Each right shift operation reduces the number to its half.


Bit Operators
Checkpoint
Question #1
First let's solve it using normal
approach.

Then let's solve it using bits


(shifting operation)
Solution
class Solution:
def countBits(self, n: int) -> List[int]:
bitCounts = []
for i in range(n+1):
count = 0
while i > 0:
if i & 1 == 1:
count += 1
i >>= 1
bitCounts.append(count)
return bitCounts
Bitwise operators properties
● Commutative
○ x^y=y^x
● Associative
○ x & (y & z) = (x & y) & z
● Do these properties hold for all bit operators?
More Bitwise Operator Properties
● Identity
○ XOR: x ^ 0 = x
○ What about the other operators?
● Inverse
○ XOR: x ^ x = 0
○ What about the other operators?
Checkpoint
Question #2
First let's solve it using
normal approach.

Then let's solve it using bits.


Solution

def missing_number(nums): def missing_number(nums):


arr_xor = 0 N = len(nums)
range_xor = 0 range_sum = N * (N + 1) // 2
arr_sum = 0
for idx, num in enumerate(nums):
arr_xor ^= num for num in nums:
range_xor ^= idx + 1 arr_sum += num

return range_xor ^ arr_xor return range_sum - arr_sum


Bit masking
Bit masking
● Way of optimizing storage
● Store information in a single bit
Test 5th Bit

num = 10001000100111
1 = 00000000000001
Test 5th Bit
num = 10001000100111
1 = 00000000000001

1<<5 = 00000000100000

10001000100111
&
00000000100000
00000000100000 (!= 0)
Implement
Bit masking operations
Checkpoint
Question #3

● Use bit mask to keep track of


used numbers
Solution
def permute(self, nums: List[int]) -> List[List[int]]:
ans, curr = [], []
used = 0

def build(i=0):
nonlocal used
if i == len(nums):
ans.append(curr.copy())
return

for idx, num in enumerate(nums):


if (used & (1 << idx)) == 0:
used ^= 1 << idx
curr.append(num)
build(i+1)
curr.pop()
used ^= 1 << idx
build()
return ans
Python Built-in Functions
Bit masking
● bin(): This built-in function can be used to convert an integer to a binary
string.
● int(): This built-in function can be used to convert a binary string to an
integer.
Bit masking
● bit_length(): This method can be called on an integer and returns the
number of bits required to represent the integer in binary, excluding the
sign bit.
● bit_count() : this method can be called on an integer and returns the
number of set bits.
Practice Problems
● Number Complement
● Hamming Distance
● Cirno’s Perfect Bitmasks Classroom
● Subsets
● Add Binary
● Single Number II
● Single Number III
● Sum of Two Integers
● Maximum Product of Word Lengths
“The greatest glory
in living lies not in
never falling, but
in rising every time
we fall.”
-Nelson Mandela

You might also like