Em chào các anh(chị), hiện em đang học môn kiến trúc máy tính và có bài này em chưa hiểu ,anh(chị) nào có thể giải thích lời giải của bài này giúp em được không ạ.
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
/* docs */
int shift = 33 + ~n;
return !(x ^ ((x << shift) >> shift));
}
Đầu tiên phải thay int bằng uint32_t thì mới đúng, u là vì >>.
Sau khi thay, do ~n = -(n+1) nên shift = 32 - n.
Giả sử x vừa đúng n0 bit. Nếu 32 - n + n0 <= 32 thì x được bảo toàn.
Để ý rằng:
x có bit thứ n-1 là 0, thì tất cả những bit cao hơn nó phải là 0 hết thì x mới fit được trong n bits.x có bit thứ n-1 là 1, thì tất cả những bit cao hơn nó phải là 1 hết thì x mới fit được trong n bits.Vậy bài toán chuyển về kiểm tra các bit thứ n, n+1, … có giống với bit thứ n-1 hết hay ko.
2 cái để ý này hơi khó thấy ngay được nếu em mới học, thử viết vài số âm/dương thành dạng 2’s complement với số bit khác nhau sẽ thấy. Ví dụ:
Cho số b31b30b29…bnbn-1bn-2…b2b1b0 ta cần tạo ra số mới bn-1bn-1bn-1…bn-1bn-1bn-2…b2b1b0, rồi đem số mới này XOR với số cho trước, để kiểm tra xem 2 số có giống nhau hay ko, nếu giống thì trả về true. (a, b giống nhau thì a xor b trả về 0 nên phải thêm toán tử NOT nữa)
Muốn làm các bit đứng trước bn-1 giống bn-1 thì ta có thể shift left cho nó bay hết mấy bit trước nó, rồi shift right về lại vị trí cũ, hy vọng các bit mới điền vào chỗ trống giống với bit cao nhất lúc này là bit thứ n-1. Từ n tới 31 có 31 - n + 1 = 32 - n bit nên phải tính trước shift = 33 + ~n vì trong 2’s complement -n = ~n + 1 nên 32 - n = 32 + ~n + 1 = 33 + ~n.
<< (32-n) hy vọng sẽ ra bn-1bn-2…b2b1b0a31-na30-n…a1a0 (ai có giá trị bao nhiêu ko cần biết vì tiếp theo nó sẽ bị xóa mất)>> (32-n) hy vọng sẽ ra bn-1bn-1bn-1…bn-1bn-1bn-2…b2b1b0
^ b31b30b29…bnbn-1bn-2…b2b1b0 sẽ ra x31x30x29…xn00…000. Nếu các bit bên trái bit thứ n-1 giống với bn-1 hết thì kết quả sẽ ra 0, còn ko sẽ ra một số khác 0. Cuối cùng đem kết quả này apply toán tử NOT vào sẽ ra true nếu kết quả XOR==0, false nếu kết quả trước đó khác 0.Vấn đề là trong C và C++, a << b với a có dấu và a < 0 là ko xác định =) Có thể compiler trường xài nó làm y hệt như trên, nhưng compiler khác nó ko làm như vậy cũng ko đốt compiler đó đc vì nó ko làm sai chuẩn vì chuẩn nói anh thích làm gì thì làm, vì dòng code này ko xác định. Nhưng có lẽ đa số là các compiler nó làm đúng như trên nên chắc ko sao :V
a >> b chứ 
Ý tưởng ban đầu có thể là kick thử xem bit 1 đầu có bị lọt ra ngoài không. Nếu không lọt tức là shift phải trở lại vẫn y nguyên => xor bằng zero. Ngược lại, bit 1 đầu bị kick thì shift phải (không dấu!) là 0 => xor khác 0.
Shift phải có hai kiểu: một là thêm 0 vào (shr), hai là chia (đôi) (gọi là sar). Không dấu thì hai kiểu như nhau, còn có dấu thì phải thêm 1 mới chia đôi. Do compiler muốn shift kiểu gì cũng được nên phải dùng unsigned mới ổn.
Nhưng như vậy thì cũng có primitive để dùng mà
shift right thì có 2 kiểu arithmetic và logical thì có thể thấy là nó có thể tùy vào implementation, chứ còn shift left mà cũng undefined thì mới bất ngờ: https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators
For negative a, the behavior of a << b is undefined.
với C: https://en.cppreference.com/w/c/language/operator_arithmetic#Shift_operators
For signed lhs with nonnegative values, the value of LHS << RHS is LHS * 2RHS
if it is representable in the promoted type of lhs, otherwise the behavior is undefined.
https://msdn.microsoft.com/en-us/library/336xbhcz.aspx
If you left-shift a signed number so that the sign bit is affected, the result is undefined.
Yes, I would say it’s undefined.
Cảm ơn anh nhé, em đã hiểu rồi
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?