Luyện tập Bit Manipulation

HàPQ -

Bài 1:
Cho 2 số n và m, chèn tất cả các bit của m vào n theo khoảng từ  i đến j. Có thể chắc chắn là số lượng bit của n luôn lớn hơn m, và i-j  = số lượng bit của m.
Ví dụ:

Input: n = 1024
m = 19
i = 2
j = 6
Output: n = 1100

Giải thích
(1024)10 = (10000000000)2
(19)10 = (10011)2
kết quả : (10001001100)2 = (1100)10

Cách làm như sau
1. xoá toàn bộ bit từ i đến j (về 0) của n
2. dịch m sang trái i bit
3. trả về kết quả m & n

Bước 1 là khó nhất, chúng ta áp dụng cách làm thông thường là tạo mặt nạ.
Mặt nạ của chúng ta gồm 3 phần, bên trái j, bên phải i là 1, ở giữa i j là 0. 

let allOnes = ~0
let left = allOnes << (j + 1)
let right = ((1 << i) - 1)
let mask = left | right

sau đó chỉ cần & n với mặt nạ vừa tạo là xong.

Bài 2:
Cho một số nguyên và một lần duy nhất đổi bit 0 thành bit 1. Cài đặt hàm tìm chuỗi 1 dài nhất sau khi thực một lần đổi bit.
Ví dụ:
Input: 1775 (tương ứng: 11011101111)
Output: 8  
Gỉai thích: nếu đổi bit thứ 9 thì có chuỗi 1 dài nhất là 6, đổi bit thứ 5 ta có chuỗi 8

Hmm, giải như thế nào đây ta?

Ý tưởng đầu tiên của mình là đếm toàn bộ số 1 bên trái và phải của toàn bộ số 0, sau đó trả về max tổng trái phải….
ví dụ 101110111, phải của 0 đầu là 3, trái là 3, phải 0 sau là 3, trái là 1, vậy kết quả sẽ là max( 3+3, 3+1) + 1 = 7.
Nếu duyệt 2 lần thì sẽ double work việc tìm 1 trái phải, nên chúng ta có cách duyệt tối ưu hơn là đếm 1 đến khi gặp 0 thì gán bên phải là hiệu của index hiện tại với index 0 tìm thấy trước đó, bên trái sẽ được tính cho đến khi gặp 0 tiếp theo, thực hiện update lại max nếu cần.

func flipToWin(_ input: Int) -> Int {
    var maxLength = 0
    
    var currentLength = 0
    var previousLength = 0
    
    var clone = input
    while clone > 0 {
        let num = clone & 1
        if num == 1 {
            currentLength += 1
        } else {
            previousLength = (clone & 2) == 0 ? 0 : currentLength
            currentLength = 0
        }
        
        maxLength = max(previousLength + currentLength, maxLength);
        clone >>= 1
    }
    
    return maxLength + 1
}

Happy Coding!