Mã thao tác nhị phân trong Python

Bài viết này sẽ đưa bạn qua một trong những chủ đề đáng sợ nhất của Phỏng vấn kỹ thuật, đó là BIT MANIPULATION

Trước tiên, tôi giả sử rằng bạn biết kiến ​​thức cơ bản về Số nhị phân, chuyển đổi từ nhị phân sang thập phân và dịch chuyển bit nếu không, vui lòng tham khảo một số tài liệu tôi đã liên kết

1. Hiểu các ca số học
2. Hiểu sự thay đổi hợp lý. (Ví dụ)

https. //youtube. be/nSKT6Ph8u9Q

3. (Đếm từ LSB)Để trích xuất bit thứ i thực hiện

def rightmost_one(num):
    return num ^ (num & (num - 1))

4. (Đếm từ LSB) Để Đặt bit thứ i thành một thực hiện

def rightmost_one(num):
    return num ^ (num & (num - 1))

5. Để xóa bit thứ i, hãy sử dụng

def rightmost_one(num):
    return num ^ (num & (num - 1))

6. Để xóa tất cả các bit từ MSB sang thứ i, hãy sử dụng

def rightmost_one(num):
    return num ^ (num & (num - 1))

7. Để xóa tất cả các bit từ bit thứ i sang LSB, hãy sử dụng

def rightmost_one(num):
    return num ^ (num & (num - 1))

8. Để cập nhật một bit cụ thể, hãy sử dụng

def rightmost_one(num):
    return num ^ (num & (num - 1))

9. Biết về toán tử XOR (Ví dụ)https. //www. học viện khan. org/máy tính/khoa học máy tính/mật mã/mật mã/a/xor-bitwise-operation

Được rồi, bây giờ chúng ta đã rõ về những điều cơ bản Bây giờ hãy bắt đầu với vấn đề đầu tiên của chúng ta về thao tác bit trong Python

ví dụ 1. Viết mã python để tìm không có bit nào được đặt thành 1

Trực giác

dịch chuyển phải là gì. Nó xóa một bit khỏi LSB và thêm số 0 vào MSB

Theo cách tương tự, nếu chúng tôi thực hiện dịch chuyển phải hợp lý cho độ dài của đầu vào, chúng tôi sẽ nhận được thông tin sau và chúng tôi có thể quan sát cách LSB được thay thế

Và nếu chúng tôi thực hiện bitwise AND trên những kết quả này, chúng tôi sẽ nhận được những điều sau đây như chúng tôi có thể quan sát trong trường hợp này, LSB được trích xuất

thuật toán. Nếu chúng ta quan sát mẫu Dịch chuyển phải và Bitwise AND, Chúng ta đi đến kết luận rằng chúng ta có thể sử dụng hai toán tử này để biết liệu bit là 0 hay 1. Vì vậy, để đếm số bit, ban đầu xác định một biến int có tên là

def rightmost_one(num):
    return num ^ (num & (num - 1))

def rightmost_one(num):
    return num ^ (num & (num - 1))

def rightmost_one(num):
    return num ^ (num & (num - 1))

Mã số. Không gian O(1), Thời gian O(n) trong đó n là độ dài của đầu vào

def num_bits(num: int) -> int:
    num_bit = 0
    while num:
        num_bit += num & 1
        num = num >> 1return num_bit

ví dụ 2. trả về 1 ngoài cùng bên phải trong số nhị phân (trả về 1 bắt đầu từ LSB)

Đối với 101101 trả lại 000001

Đối với 101010 trả lại 000010

Cho 010000 trả về 010000

Trực giác.

def rightmost_one(num):
    return num ^ (num & (num - 1))

Và điều gì sẽ xảy ra nếu chúng ta thực hiện thao tác AND trên các số này?, như chúng ta có thể quan sát trong ví dụ bên dưới, điều này trả về tất cả các chữ số trong đầu vào của chúng ta ngoại trừ số 1 cuối cùng bằng 0

Ok cho đến bây giờ những gì chúng ta đã làm là lấy một số trừ đi 1 và thực hiện AND trên nó. Bây giờ những gì chúng tôi muốn là để có được 1 bên phải

Trước đó, hãy chiêm ngưỡng bảng chân lý XOR. Nếu hai giá trị bằng nhau thì câu trả lời là 0 và nếu hai giá trị không bằng nhau thì câu trả lời là 1

Vì vậy, điều gì sẽ xảy ra nếu chúng ta XOR giá trị thu được từ

def rightmost_one(num):
    return num ^ (num & (num - 1))

def rightmost_one(num):
    return num ^ (num & (num - 1))

Mã hóa thời gian thực

def rightmost_one(num):
    return num ^ (num & (num - 1))

ví dụ 3. Tính toán tính chẵn lẻ của một từ

Tính chẵn lẻ của một số nhị phân là 1 nếu số đơn vị trong số đó là số lẻ khác 0

101101101 có tính chẵn lẻ là 0

111101101 có tính chẵn lẻ là 1

Tôi sẽ đưa ra ba ví dụ, mỗi ví dụ cải thiện về độ phức tạp của thời gian

Giải pháp 1

trực giác 1. Chúng tôi đã biết rằng việc thực hiện Bitwise AND của

def rightmost_one(num):
    return num ^ (num & (num - 1))

def rightmost_one(num):
    return num ^ (num & (num - 1))

Bây giờ, hãy xem xét SỐ 451 và viết ra các bit của nó trên một tờ giấy và XOR giá trị của nó bằng 0, hãy ghi nhớ kết quả đó và thực hiện tương tự cho các bit cho đến MSB

Do đó, chúng tôi quan sát thấy rằng thuật toán này sẽ cung cấp cho chúng tôi tính chẵn lẻ ngay bây giờ nếu tại thời điểm này nếu bạn có câu hỏi như “làm thế nào chúng ta có thể lặp qua số nhị phân mà không có mảng hoặc vòng lặp?”

Ghi chú. chúng tôi đang lấy kết quả là 0 vì do thuộc tính của XOR, 1 trong đầu vào sẽ triệt tiêu lẫn nhau và nếu có một XOR lẻ của cái đó bằng 0 sẽ cho chúng tôi 1

Mã số. Giờ O(n). n là độ dài của đầu vào

def rightmost_one(num):
    return num ^ (num & (num - 1))

Giải pháp 2

Trực giác. Như chúng ta đã quan sát trong các ví dụ trước khi chúng ta trừ một số nhị phân bằng 1, chúng ta nhận được số ngoại trừ dấu 1 của nó. Theo cách tương tự, điều gì sẽ xảy ra nếu chúng ta thực hiện thao tác AND trên kết quả này với số ban đầu

def rightmost_one(num):
    return num ^ (num & (num - 1))

hãy ghi nhớ thuộc tính này, điều gì sẽ xảy ra nếu chúng ta lấy một biến có giá trị ban đầu bằng 0 và thực hiện phép toán XOR theo bit cho đến khi có 1 trong đầu vào, chúng ta sẽ nhận được câu trả lời của mình

ok, tuyệt vời, bây giờ chúng ta có thể viết một thuật toán rất hiệu quả, thuật toán này sẽ chỉ lặp lại không có số 1 nào trong đầu vào

Mã số. Chúng ta có thể quan sát thấy độ phức tạp của thời gian giảm đáng kể

def rightmost_one(num):
    return num ^ (num & (num - 1))

Giải pháp 3

trực giác 3. Hãy khai thác ở đây các thuộc tính cơ bản của XOR xem xét chúng ta có một số abcxyz hơn

Xem xét ví dụ

Hãy xem xét chúng ta có đầu vào 8 bit và nếu chúng ta muốn tính chẵn lẻ của số này, tất cả những gì chúng ta cần làm là thực hiện phép XOR bit của 4 bit đầu tiên với 4 bit cuối cùng, sau đó là 2 bit đầu tiên với 2 bit cuối cùng, v.v.

Mã số

def rightmost_one(num):
    return num ^ (num & (num - 1))

Ví dụ 4. Cho hai số nguyên X và Y tìm số bit cần thiết để chuyển đổi số nguyên X thành Y

Trực giác. Đây là một vấn đề tương đối đơn giản nếu chúng ta hiểu các thuộc tính của XOR

Xem xét ví dụ

x = 1011010

y = 1001000

Để chuyển đổi số nguyên x thành y, chúng ta cần khớp các bit là 1

từ ví dụ dưới đây, chúng tôi quan sát thấy rằng hai bit được yêu cầu để chuyển đổi

Điều gì sẽ xảy ra nếu chúng ta XOR “X” và “Y”, chúng ta sẽ chỉ nhận được những bit khác nhau

Do đó, chúng ta có thể sử dụng thuật toán được sử dụng trong ví dụ đầu tiên để đếm số bit

Mã số

def rightmost_one(num):
    return num ^ (num & (num - 1))

Ví dụ 5. bạn được cung cấp một số nguyên đầu vào và hai vị trí, mục tiêu của bạn là hoán đổi các vị trí này

ĐẦU VÀO. số, vị trí thứ i, vị trí thứ j

Hoán đổi vị trí 5 và 1

Trực giác. Để hoán đổi hai bit này, trước tiên chúng ta cần tìm giá trị của bit ở vị trí đã cho, chúng ta có thể thực hiện việc này theo nhiều cách khác nhau nhưng tôi sẽ chỉ ra hai cách ngắn gọn, một cách sử dụng dịch chuyển trái và cách khác sử dụng dịch chuyển phải

Sử dụng Shift phải

Dịch chuyển sang phải số đầu vào với vị trí thứ i và thực hiện thao tác AND theo bit, tương tự cho vị trí thứ j.

def rightmost_one(num):
    return num ^ (num & (num - 1))

Bằng cách này, chúng ta có thể trích xuất các vị trí

Sử dụng Shift trái

Dịch trái 1 bằng “i” và thực hiện thao tác AND với num tương tự với “j”.

def rightmost_one(num):
    return num ^ (num & (num - 1))

Bây giờ chúng tôi đã trích xuất các bit, tất cả những gì chúng tôi phải làm là lật các bit, chúng tôi sẽ chỉ tiếp tục nếu các bit khác nhau, nếu không thì trả về số đầu vào

nếu các bit khác nhau, chúng tôi sẽ sử dụng thuộc tính của XOR và OR để tạo mặt nạ bit

Sử dụng phương pháp được trình bày trong Sử dụng phép dịch trái, chúng ta có thể đặt 1 ở vị trí của “i” và “j”. Và nếu chúng ta thực hiện theo chiều bit HOẶC chúng ta sẽ nhận được mặt nạ cho vị trí thứ i và thứ j

Thực hiện XOR bit của số với mặt nạ và chúng tôi sẽ nhận được câu trả lời cần thiết với các bit được đảo ngược

Mã số

def rightmost_one(num):
    return num ^ (num & (num - 1))

Ví dụ 6. các bit đảo ngược của đầu vào đã cho

10101010 -> 01010101

01101010 -> 01010110

Trực giác và thuật toán

Vấn đề trong EOP là 64 bit và trong leetcode là 32 bit nhưng để đơn giản, chúng tôi sẽ sử dụng 6 bit

>> nghĩa là gì trong Python?

Toán tử nhị phân trong Python là gì?