30daychallenge (23) | Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

Bit ơi là bit. Giả sử dãy [80,85] hệ nhị phân thành: [1010000, 1010001, 1010010, 1010011, 1010100, 1010101]. Viết theo hàng dọc:

1010|000

1010|001

1010|010

1010|011

1010|100

 1010|101 

Phần bên trái khi tác động toán tử & sẽ không ảnh hưởng gì cả. Vậy 1010000 chính là kết quả của bài toán theo tính chất &. Bài toán trở nên rất đơn giản, dịch bit về bên phải cho đến khi  đoạn đầu và đoạn cuối bằng nhau, ở đây là 1010000 và 1010101. Ghi nhớ số lần dịch là carry. Kết quả bài toán là dịch ngược bên trái lại bằng số lần đã dịch bên phải.

	// duynotes.blogspot.com
	class Solution {
	public int rangeBitwiseAnd(int m, int n) {
	int carry = 0;
	while (n!=m){
	n>>=1;
	m>>=1;
	carry++;
	}
	return n<<carry;
	}
	}

view raw BitwiseAndNumberOfRange.java delivered with ❤ by emgithub

Cảm ơn !