Bitshifting trong Java

Question

Tôi đang cố gắng hiểu cách hoạt động của bit shift. Có thể ai đó xin giải thích ý nghĩa của dòng này:

while ((n&1)==0) n >>= 1; 

nơi n là một số nguyên và đưa cho tôi một ví dụ về một n khi sự thay đổi được thực hiện.

Answer 1

Giả sử n = 12. Các bit cho điều này sẽ là 1100 (1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 = 12). Lần đầu tiên qua vòng lặp n & 1 == 0 vì số cuối cùng là 1100 và 0 khi bạn VÀ với 1, bạn nhận được 0. Vì vậy, n >> = 1 sẽ làm n thay đổi từ 1100 (12) thành 110 (6). Như bạn có thể nhận thấy, dịch chuyển phải có cùng tác dụng như chia cho 2. Bit cuối cùng vẫn bằng 0, do đó, & 1 sẽ vẫn là 0, vì vậy nó sẽ dịch chuyển một lần nữa. n >> = 1 sẽ làm cho nó thay đổi một chữ số khác sang phải thay đổi n từ 110 (6) đến 11 (3).

Bây giờ bạn có thể thấy bit cuối cùng là 1, vì vậy, & 1 sẽ là 1, làm cho vòng lặp while ngừng hoạt động. Mục đích của vòng lặp dường như là dịch chuyển số sang bên phải cho đến khi nó tìm thấy bit được bật đầu tiên (cho đến khi kết quả là lẻ).

Answer 2

n & 1 thực sự là bitwise AND operataion. Ở đây, mẫu bit của n sẽ là ANDED dựa trên mẫu bit của 1. Kết quả của ai sẽ được so sánh với số không. Nếu có thì n phải dịch chuyển 1 lần. Bạn có thể thực hiện một sự thay đổi đúng như phân chia bởi 2 và như vậy.

Answer 3

Breaking nó xuống:

n & 1 sẽ làm một so sánh nhị phân giữa n và 1 mà là 00000000000000000000000000000001 ở dạng nhị phân. Như vậy, nó sẽ trả về 00000000000000000000000000000001 khi n kết thúc bằng 1 (số lẻ hoặc số âm dương) và 00000000000000000000000000000000 nếu không.

(n & 1) == 0 do đó sẽ đúng nếu n là số chẵn (hoặc âm lẻ) và sai khác.

n >> = 1 tương đương với n = n >> 1. Như vậy nó dịch chuyển tất cả các bit sang phải, tương đương với một phân chia bằng hai (làm tròn xuống).

Nếu ví dụ: n bắt đầu như 12 sau đó trong nhị phân nó sẽ là 1100. Sau một vòng lặp nó sẽ là 110 (6), sau khi nó sẽ là 11 (3) và sau đó vòng lặp sẽ dừng lại.

Nếu n bằng 0 thì sau vòng lặp tiếp theo, nó sẽ là 0 và vòng lặp sẽ là vô hạn.

Answer 4

ví dụ nếu n là

n= b11110000 

sau đó

n&1= b11110000 & 
     b00000001 
     --------- 
     b00000000 

n>>=1 b11110000 >> 1 
     --------- 
     b01111000 

n= b01111000 

nếu vòng lặp tiếp tục nó phải được

n= b00001111 

Answer 5

Lets n được 4 mà ở dạng nhị phân được biểu diễn dưới dạng:

00000000 00000000 00000000 00000100 

(n&1) bitwise ands n với 1.
1 có biểu diễn nhị phân của:

00000000 00000000 00000000 00000001 

Kết quả của anding Bitwise là 0:

00000000 00000000 00000000 00000100 = n 
00000000 00000000 00000000 00000001 = 1 
------------------------------------ 
00000000 00000000 00000000 00000000 = 0 

nên các điều kiện của while là sự thật.
Hiệu quả (n&1) được sử dụng để trích xuất bit ít quan trọng nhất của n.

Trong vòng lặp while bạn phải dịch (>>) n bởi 1. Chuyển số phải bằng k cũng giống như chia số bằng 2^k.

n hiện tại là 00000000 00000000 00000000 00000100 khi dịch chuyển đúng một lần trở thành 00000000 00000000 00000000 00000010 là 2.

Tiếp theo, chúng tôi trích xuất LSB (bit ít quan trọng nhất) là n lần nữa là 0 và dịch chuyển sang phải để cung cấp cho 00000000 00000000 00000000 0000001 là 1.

Tiếp theo, chúng tôi lại trích xuất LSB của n, hiện tại là 1 và ngắt vòng lặp.

Vì vậy, hiệu quả bạn tiếp tục chia số của bạn n bởi 2 cho đến khi nó trở thành lẻ dưới dạng số lẻ có bộ LSB của chúng.

Cũng lưu ý rằng nếu n là 0 để bắt đầu với bạn sẽ đi vào một vòng lặp vô hạn vì không có vấn đề bao nhiêu lần bạn chia 0 bởi 2 bạn sẽ không nhận được một số lẻ.

Answer 6

Giả sử bằng 42 (chỉ vì):

int n = 42; 

while ((n & 1) == 0) { 
    n >>= 1; 
} 

Iteration 0:

• n = 42 (hoặc 0000 0000 0000 0000 0000 0000 0010 1010)
• n & 1 == 0 là true (vì n & 1 = 0 hoặc 0000 0000 0000 0000 0000 0000 0000 0000)

Iteration 1:

• n = 21 (hoặc 0000 0000 0000 0000 0000 0000 0001 0101)
• n & 1 == 0 là false (vì n & 1 == 1 hoặc 0000 0000 0000 0000 0000 0000 0000 0001)

Những gì nó:

Về cơ bản, bạn lặp chia n cho 2 miễn là n là một số chẵn:

• n & 1 là kiểm tra chẵn lẻ đơn giản,
• n >> = 1 thay đổi các bit bên phải, chỉ chia cho 2.