Thuật toán như sau:

mã hóa int(int a, int b) {
    ngắn int c, c2;
    uint8_t d;

    c = a^b;
    c2 = c;

    d = 0;
    trong khi(c) {
        c &= c - 1;
        d++;
    }

    trả lại d;
}

Làm cách nào để tìm biến a và b nào tôi nên gửi trong hàm này để xác định giá trị đầu ra của d?

Nói cách khác, nếu tôi muốn d=11, làm cách nào tôi có thể đảo ngược thuật toán?

câu trả lời hay nhất

cái này:

trong khi(c) {
    c &= c - 1;
    d++;
}

tính toán c Số lượng bit 1 trong . c=10110 , d sẽ là 3.

cái này:

c = a^b;

LÀM độc quyền hoặchiện hữu Một giữa và b .Điều này có nghĩa là trong Một Tất cả các tổng 1 bit có cùng vị trí trong bsẽ bằng 0, tất cả đều có Một Các vị trí có giá trị khác nhau trong và bsẽ trở thành 1 Ví dụ:

101110^
011010
========
110100

Về cơ bản, thuật toán tìm a^b số lượng bit 1 trong . Để buộc nó xuất ra một giá trị nhất định, chỉ cần thực hiện một = 0Sau đób = số có d 1-bit .

用 d Để có được một số có 1 chữ số, hãy xem xét b = (2 lũy thừa của d) - 1 .

vì vậy nếu bạn muốnd=11 , Sau đó một = 0Và b = (2 lũy thừa 11) - 1 = 2048 - 1 = 2047 .

Để tính lũy thừa của 2 một cách hiệu quả theo chương trình, hãy sử dụng công thức sau:

2 lũy thừa của k == 1 << k

Vì vậy, về cơ bản:mã hóa (a, b) == d nếu a = 0 và b = (1 << d) - 1 .

Về c - đảo ngược AND bitwise, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/2612807/