Tại sao chức năng này lớn hơn chức năng?

Question

Tôi đang làm bài tập về nhà, nơi chúng ta phải tạo một hàm gọi là isGreater (x, y) trả về nếu x lớn hơn y, nhưng chúng ta chỉ có thể sử dụng toán tử bitwise cùng với + và! Tôi đã giải quyết vấn đề, sử dụng quy tắc nếu x và y có các dấu hiệu khác nhau, sau đó x> = 0 và y < 0 hoặc nếu x và y có cùng dấu thì chỉ khi y-x là âm.

Tuy nhiên, khi tôi nhìn xung quanh cách người khác giải quyết nó, tôi nhận thấy phương pháp sau đây hoạt động chính xác vì bất kỳ lý do gì.

y = ~y; 
return !(((x&y) + ((x^y) >> 1)) >> 31); 

Tôi không thể cho cuộc sống của tôi hiểu tại sao điều này hiệu quả, tôi thấy điều này có liên quan đến bit đầu tiên trong x không được đặt trong y hoặc gì đó?

Lưu ý: Rõ ràng đây chỉ là giải pháp hợp lệ nếu x và y là ints, không phải là unsigned int.

Answer 1

31 có nghĩa là chúng tôi chỉ quan tâm đến biển báo. Nếu ((x & y) + ((x^y) >> 1))> 0 thì x> ~ y.
x & ~ y sẽ tạo một số trong đó MSB sẽ là bit đầu tiên trong đó x có bit thiết lập và y có 0. x^~ y sẽ tạo ra một số trong đó các bit chưa đặt sẽ đại diện cho các bit trong đó x và y khác nhau. Nếu chúng ta thay đổi nó bằng một cái chúng ta cần cho tổng của chúng để trở nên tích cực. Điều này sẽ chỉ xảy ra nếu bit không đầu tiên của x & y (có nghĩa là bit đầu tiên trong đó x được đặt và x và y khác nhau) đáp ứng với bit được đặt trong ((x^y) >> 1) (nghĩa là bit được đặt trong một nhưng không được đặt ở vị trí khác).
Và nếu bit cao nhất được đặt bằng x nhưng không được đặt trong y, cũng là bit cao nhất được đặt trong một nhưng không được đặt ở điểm khác - điều này có nghĩa là x lớn hơn y.

Ví dụ:

(shft is x^~y >> 1, res is shft + x&~y) 

x: 000110 
y: 001010 
~y: 110101 
x&~y:000100 
x^~y:110011 
shft:111001 
res: 111101 -> negative 

x: 000110 
y: 000010 
~y: 111101 
x&~y:000100 
x^~y:111011 
shft:111101 
res: 000001 -> positive 

Đây là lý do tại sao nó does't làm việc cho unsigned BTW (không có dấu hiệu đó).