ý nghĩa của (số) & (-number)

Question

Ý nghĩa của (number) & (-number) là gì? Tôi đã tìm kiếm nó nhưng không thể tìm ra ý nghĩa

Tôi muốn sử dụng i & (-i) trong vòng lặp for như:

for (i = 0; i <= n; i += i & (-i)) 

Answer 1

Giả sử bổ sung 2 (hoặc rằng i là unsigned), -i bằng ~i+1.

i & (~i + 1) là mẹo để trích xuất bit được đặt thấp nhất là i.

Nó hoạt động vì những gì +1 thực sự làm là đặt bit rõ ràng thấp nhất và xóa tất cả các bit thấp hơn. Vì vậy, bit duy nhất được đặt trong cả hai i và ~i+1 là bit được đặt thấp nhất từ ​​i (nghĩa là, bit rõ ràng thấp nhất trong ~i). Các bit thấp hơn mức rõ ràng trong số ~i+1 và các bit cao hơn số không bằng nhau giữa i và ~i.

Sử dụng nó trong vòng lặp có vẻ lẻ trừ khi vòng lặp sửa đổi i, bởi vì i = i & (-i) là một hoạt động không cần thiết: làm hai lần cho kết quả tương tự một lần nữa.

[Chỉnh sửa: trong nhận xét ở nơi khác bạn chỉ ra rằng mã thực sự là i += i & (-i). Vì vậy, những gì làm cho không khác i là để xóa nhóm bit thiết lập thấp nhất của i và đặt bit rõ ràng tiếp theo ở trên đó, ví dụ 101100 -> 110000. Đối với i không có bit rõ ràng cao hơn bit đặt thấp nhất (bao gồm i = 0), nó đặt i thành 0. Vì vậy, nếu không thực tế là i bắt đầu tại 0, mỗi vòng lặp sẽ tăng i bởi ít nhất ít nhất gấp đôi vòng lặp trước đó, đôi khi nhiều hơn n và ngắt hoặc chuyển đến 0 và lặp lại vĩnh viễn.

Nó thường sẽ không thể tha thứ để viết mã như thế này mà không có một bình luận, nhưng tùy thuộc vào lĩnh vực của vấn đề lẽ đây là một "rõ ràng" chuỗi các giá trị để lặp kết thúc.]

Answer 2

Tôi nghĩ tôi chỉ mất một chút thời gian để hiển thị cách hoạt động của nó. Mã này cung cấp cho bạn giá trị bit được đặt thấp nhất:

int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10) 
int j = -i;   //-(-1) == 1 
int k = i&j;  // 1111(2) = -1(10) 
        // & 0001(2) = 1(10) 
        // ------------------ 
        // 0001(2) = 1(10). So the lowest set bit here is the 1's bit 


int i = 0x80;  //Last 2 bytes are 1000 0000(base 2), 128(base 10) 
int j = -i;   //-(128) == -128 
int k = i&j;  // ...0000 0000 1000 0000(2) = 128(10) 
        // & ...1111 1111 1000 0000(2) = -128(10) 
        // --------------------------- 
        // 1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit 

int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10) 
int j = -i;   //-(-64) == 64 
int k = i&j;  // 1100 0000(2) = -64(10) 
        // & 0100 0000(2) = 64(10) 
        // ------------------ 
        // 0100 0000(2) = 64(10). So the lowest set bit here is the 64's bit 

Nó hoạt động tương tự cho giá trị chưa ký, kết quả luôn là giá trị của bit được đặt thấp nhất.

Với vòng lặp của bạn:

for(i=0;i<=n;i=i&(-i)) 

Không có bit set (i=0), do đó bạn đang đi để lấy lại một 0 cho bước tăng của hoạt động này. Vì vậy, vòng lặp này sẽ tiếp tục mãi mãi trừ khi n=0 hoặc i được sửa đổi.

Answer 3

Giả sử rằng các giá trị âm đang sử dụng phần bổ sung của hai. Sau đó, -number có thể được tính là (~number)+1, lật các bit và thêm 1.

Ví dụ: nếu number = 92.Sau đó, đây là những gì nó sẽ giống như trong nhị phân:

number    0000 0000 0000 0000 0000 0000 0101 1100 
~number    1111 1111 1111 1111 1111 1111 1010 0011 
(~number) + 1  1111 1111 1111 1111 1111 1111 1010 0100 
-number    1111 1111 1111 1111 1111 1111 1010 0100 
(number) & (-number) 0000 0000 0000 0000 0000 0000 0000 0100 

Bạn có thể thấy từ ví dụ trên (number) & (-number) cung cấp cho bạn ít nhất.

Bạn có thể xem mã chạy trực tuyến trên IDE Một: http://ideone.com/WzpxSD

Dưới đây là một số mã C:

#include <iostream> 
#include <bitset> 
#include <stdio.h> 
using namespace std; 

void printIntBits(int num); 
void printExpression(char *text, int value); 

int main() { 
    int number = 92; 

    printExpression("number", number); 
    printExpression("~number", ~number); 
    printExpression("(~number) + 1", (~number) + 1); 
    printExpression("-number", -number); 
    printExpression("(number) & (-number)", (number) & (-number)); 

    return 0; 
} 

void printExpression(char *text, int value) { 
    printf("%-20s", text); 
    printIntBits(value); 
    printf("\n"); 
} 

void printIntBits(int num) { 
    for(int i = 0; i < 8; i++) { 
     int mask = (0xF0000000 >> (i * 4)); 
     int portion = (num & mask) >> ((7 - i) * 4); 
     cout << " " << std::bitset<4>(portion); 
    } 
} 

Ngoài ra ở đây là một phiên bản trong C# .NET: https://dotnetfiddle.net/ai7Eq6