Bit twiddling để kiểm tra xem một số có trong phạm vi cụ thể

Question

Tôi tìm thấy một thú vị bit twiddling trong "source\common\unicode\utf.h" tập tin của thư viện ICU (thành phần quốc tế cho Unicode). Các twiddling bit được thiết kế để kiểm tra xem một số là trong một phạm vi cụ thể.

// Is a code point in a range of U+d800..U+dbff? 
#define U_IS_LEAD(c) (((c)&0xfffffc00)==0xd800) 

tôi đã tìm ra những con số kỳ diệu (0xfffffc00) đến từ:

MagicNumber = 0xffffffff - (HighBound - LowBound) 

Tuy nhiên, tôi cũng nhận thấy rằng công thức không áp dụng cho tất cả các phạm vi tùy ý. Có ai ở đây biết trong hoàn cảnh nào công thức hoạt động không?

Có một chút twiddling để kiểm tra xem một số là trong phạm vi cụ thể?

Answer 1

Để các thủ thuật này áp dụng, các số phải có một số tính năng phổ biến trong biểu diễn nhị phân của chúng.

0xD800 == 0b1101_1000_0000_0000 
0xDBFF == 0b1101_1011_1111_1111 

Thử nghiệm này thực sự là che giấu mười bit thấp hơn. Điều này thường được viết là

onlyHighBits = x & ~0x03FF 

Sau khi hoạt động này ("và không") mười bit dưới của onlyHighBits được đảm bảo bằng không. Điều đó có nghĩa rằng nếu con số này bằng với phạm vi thấp hơn của khoảng thời gian này, nó đã ở đâu đó trong khoảng thời gian trước đó. Thủ thuật này hoạt động trong mọi trường hợp khi giới hạn dưới và giới hạn cao hơn của khoảng bắt đầu với cùng số trong nhị phân, và tại một số điểm giới hạn dưới chỉ có số 0 trong khi giới hạn cao hơn chỉ có giới hạn. Trong ví dụ của bạn, đây là vị trí thứ mười từ bên phải.

Answer 2

Công thức hoạt động bất cứ khi nào phạm vi bạn đang tìm bắt đầu ở bội số của lũy thừa 2 (nghĩa là, 1 hoặc nhiều bit ở cuối thấp của dạng nhị phân của số kết thúc bằng 0) và kích thước của phạm vi là 2^n-1 (tức là, thấp & cao == thấp và thấp | cao == cao).

Answer 3

Nếu bạn không có 2^x ranh giới loại có thể sử dụng các thủ thuật sau đây:

nếu x >= 0 và x < N bạn có thể kiểm tra cả hai bởi:

if Longword(x) < Longword(N) then ... 

này hoạt động do thực tế rằng số âm trong các con số đã ký tương ứng với số lớn nhất trong các kiểu dữ liệu chưa ký.

Bạn có thể mở rộng này (khi kiểm tra Phạm vi đó là TÀN TẬT) tới:

if Longword(x - A) < Longword ((B - A)) then ... 

Bây giờ bạn đã cả các bài kiểm tra (khoảng [ A, B >) trong một SUB và CMP cộng với một Jcc duy nhất, giả định (B - A) được tính toán trước.

Tôi chỉ sử dụng các loại tối ưu hóa này khi thực sự cần; ví dụ: họ có xu hướng làm cho mã của bạn ít có thể đọc được và nó chỉ cạo ra một vài chu kỳ đồng hồ cho mỗi thử nghiệm.

Lưu ý C như trình đọc ngôn ngữ: Từ dài là kiểu dữ liệu 32 bit không được ký của Delphi.