201. Bitwise AND of Numbers Range

Problem

Bài toán yêu cầu tính toán phép AND bitwise của tất cả các số trong đoạn [left, right] . Nếu làm theo cách duyệt từng số rồi AND thì sẽ rất chậm với các đoạn lớn. Tuy nhiên, có thể nhận ra môt số tính chất giúp giải nhanh hơn

Phép AND của một dãy số liên tiếp sẽ làm tất cả các bit thay đổi trong đoạn đó thành 0 và kết quả cuối cùng

Chỉ những bit giống nhau ở cả left và right (từ trái → phải, tức phần prefix chung) mới có thể giữ lại, còn lại đều sẽ thành 0

Approach - Xóa dần bit 1 thấp nhất của right (hoặc high)

Lặp đến khi left ≥ right

Ở mỗi vòng lặp, thực hiện right &= (right - 1) (tức là xóa bit 1 thấp nhất của right)

Khi right ≤ left, kết quả là right (lúc này right và left có prefix giống nhau, các bit khác đã bị xóa hết)

Solution

typescripttypescript

1function rangeBitwiseAnd(left: number, right: number): number {
2    while(left < right) right &= right - 1
3    return right;
4};

💡

right = right & (right - 1) ?

right - 1 sẽ chuyển bit 1 thấp của right thành 0, và các bit sau nó thành 1

Khi thực hiện right & (right - 1) , bit 1 thấp nhất của right sẽ bị xóa (thành 0), các bit khác giữ nguyên

Loading content...

201. Bitwise AND of Numbers Range

Related Posts

Related Posts

201. Bitwise AND of Numbers Range

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists