Whats chức năng đảo ngược của x XOR (x/2)?

Question

Whats chức năng đảo ngược của x XOR (x/2)?

Có hệ thống quy tắc để giải phương trình, tương tự đại số hay không, nhưng với toán tử logic?

Answer 1

Giả sử chúng tôi có số x của N bit. Bạn có thể viết này như:

b(N-1) b(N-2) b(N-3) ... b(0) 

nơi b(i) là bit số i trong số (trong đó 0 là bit ít quan trọng).

x/2 giống với x dịch chuyển sang trái 1 bit. Hãy giả sử số chưa ký. Vì vậy:

x/2 = 0 b(N-1) b(N-2) ... b(1) 

Bây giờ chúng ta XOR x với x/2:

x^(x/2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1) 

Lưu ý rằng các bit ngoài cùng bên phải (bit quan trọng nhất) của việc này là b(N-1)^0 đó là b(N-1). Nói cách khác, bạn có thể nhận được bit b(N-1) từ kết quả ngay lập tức. Khi bạn có bit này, bạn có thể tính toán b(N-2) vì bit thứ hai của kết quả là b(N-2)^b(N-1) và bạn đã biết b(N-1). Và cứ thế, bạn có thể tính toán tất cả các bit b(N-1) đến b(0) của số gốc x.

Answer 2

tôi có thể cung cấp cho bạn một thuật toán theo bit:

Giả sử bạn có một mảng của n bit:

b = [b1 .. bn] // b1-bn are 0 or 1 

Mảng ban đầu là:

x0 = b0 
x1 = b1^x0 
x2 = b2^x1 

hoặc nói chung

x[i] = b[i]^x[i-1] 

Answer 3

Giả sử e Y = X^(X/2)

Nếu bạn muốn tìm X, thực hiện điều này

X = 0 

do 

    X ^= Y 
    Y /= 2 

while Y != 0 

Tôi hy vọng nó sẽ giúp!

Answer 4

Tôi biết đó là một chủ đề cũ, nhưng tôi tình cờ gặp cùng một câu hỏi và tôi đã tìm ra một mẹo nhỏ. Nếu bạn có n bit, thay vì yêu cầu n bit hoạt động (như câu trả lời bởi Jesper), bạn có thể làm điều đó với log2 (n) số hoạt động:

Giả sử rằng y là bằng x XOR (x/2) ở đầu chương trình, bạn có thể thực hiện chương trình C sau:

INPUT : y 

int i, x; 
x = y; 
for (i = 1; i < n; i <<= 1) 
    x ^= x >> i; 

OUTPUT : x 

và tại đây bạn có giải pháp.

• ">>" là thao tác dịch chuyển bit đúng. Ví dụ, số 13, 1101 ở dạng nhị phân, nếu được dịch chuyển bằng 1 ở bên phải, sẽ trở thành 110 ở dạng nhị phân, do đó 13 >> 1 = 6. x >> i tương đương với x/2^i (phân chia các số nguyên, tất nhiên)
• "< <" là bit hoạt động chuyển trái (i < < = 1 tương đương với i * = 2)

Tại sao nó hoạt động? Chúng ta hãy làm ví dụ n = 5 bit, và bắt đầu với y = b4 b3 b2 b1 b0 (trong hệ nhị phân: trong x sau đây được viết trong hệ nhị phân cũng có, nhưng tôi được viết bằng chữ số thập phân)

• initialisation:

x = b4 b3 b2 b1 b0

• bước đầu tiên: i = 1

x >> 1 = b4 b3 b2 b1 vì vậy chúng tôi có x = b4 b3 b2 b1 b0 XOR b3 b2 b1 b0 = b4 (b3^b4) (b2^b3) (b1^b2) (b0^b1)

• bước thứ hai: i = 2

x >> 2 = b4 (b3^b4) (b2^b3) vì vậy chúng tôi có x = b4 (b3^b4) (b2^b3) (b1^b2) (b0^b1) XOR b4 (b3^b4) (b2^b3) = b4 (b3^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3)

• thứ ba bước: i = 4

x >> 4 = b4 vì vậy chúng tôi có x = b4 (b3^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3) XOR b4 = b4 (b3)^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3^b4)

• Sau đó i = 8, mà là nhiều hơn 5, chúng tôi thoát khỏi vòng lặp.

Và chúng tôi có kết quả mong muốn.

Vòng lặp có log2 (n) lặp lại vì tôi bắt đầu ở 1 và được nhân với 2 tại mỗi bước, vì vậy để tôi đạt đến n, chúng ta phải thực hiện log2 (n) lần.