01/10/2018, 17:26

Bài toán FitsBits

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));
}

rogp10 viết 19:29 ngày 01/10/2018

Đầ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.

‏ viết 19:29 ngày 01/10/2018

Để ý rằng:

nếu 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.
nếu 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ụ:

17 = (0010010) biểu diễn với 7 bit, nếu biểu diễn với 3 bit (0010010) sẽ ko đủ vì có số 1 phía trước bit 0 thứ 2 (thứ 0 là bit đầu tiên bên phải)
2 = (0000010) biểu diễn với 7 bit, nếu biểu diễn với 3 bit (0000010) sẽ đủ vì các bit cao hơn bit thứ 2 đều có giá trị là 0 giống với bit thứ 2.
-36 = (1011100) biểu diễn với 7 bit, nếu biểu diễn với 3 bit (1011100) sẽ ko đủ vì có số 1 phía trước bit 0 thứ 2
-3 = (1111101) biểu diễn với 7 bit, nếu biểu diễn với 3 bit (1111101) sẽ đủ vì các bit cao hơn bit thứ 2 đều có giá trị là 1 giống với bit thứ 2.

Cho số b₃₁b₃₀b₂₉…b_nb_n-1b_n-2…b₂b₁b₀ ta cần tạo ra số mới b_n-1b_n-1b_n-1…b_n-1b_n-1b_n-2…b₂b₁b₀, 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 b_n-1 giống b_n-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.

b₃₁b₃₀b₂₉…b_nb_n-1b_n-2…b₂b₁b₀ << (32-n) hy vọng sẽ ra b_n-1b_n-2…b₂b₁b₀a_31-na_30-n…a₁a₀ (a_i có giá trị bao nhiêu ko cần biết vì tiếp theo nó sẽ bị xóa mất)
b_n-1b_n-2…b₂b₁b₀a_31-na_30-n…a₁a₀ >> (32-n) hy vọng sẽ ra b_n-1b_n-1b_n-1…b_n-1b_n-1b_n-2…b₂b₁b₀
b_n-1b_n-1b_n-1…b_n-1b_n-1b_n-2…b₂b₁b₀ ^ b₃₁b₃₀b₂₉…b_nb_n-1b_n-2…b₂b₁b₀ sẽ ra x₃₁x₃₀x₂₉…x_n00…000. Nếu các bit bên trái bit thứ n-1 giống với b_n-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

rogp10 viết 19:28 ngày 01/10/2018

a << b với a có dấu và a < 0

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à

‏ viết 19:38 ngày 01/10/2018

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