Được rồi, hãy xem xét một số 64 bit có các bit tạo thành bảng 8x8.
Ví dụ
0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0
viết như
abcdefgh
----------------
0 1 1 0 1 0 1 0
0 1 1 0 1 0 1 1
0 1 1 1 1 0 1 0
0 1 1 0 1 0 1 0
1 1 1 0 1 0 1 0
0 1 1 0 1 0 1 0
0 1 1 0 1 1 1 0
0 1 1 0 1 0 1 0
Bây giờ nếu chúng ta chỉ muốn cô lập, ví dụ:cột d(00100000
) (hoặc bất kỳ hàng/đường chéo nào)?
Điều này có thể được thực hiện?Nếu vậy thì làm thế nào?
gợi ý:
(a) Mục tiêu chính của tôi ở đây - mặc dù ban đầu không được đề cập đến - là tốc độ thô. Tôi đang tìm thuật toán nhanh nhất vì chức năng "truy xuất" đang được thực thi hàng triệu lầnmỗi giây。
(b) Điều này gần với ý tôi hơn:https://www.chessprogramming.org/Kindergarten_Bitboards
Đây là một giải pháp chỉ có 4 bước chính:
const uint64_t mặt nạ cột = 0x8080808080808080ull;
const uint64_t phép thuật = 0x2040810204081ull;
int get_col(uint64_t bảng, int col) {
uint64_t cột = (bảng << cột) & mặt nạ cột;
cột *= phép thuật;
trả về (cột >> 56) & 0xff;
}
Đây là cách nó hoạt động:
- Bảng được di chuyển sao cho các cột được căn chỉnh về bên trái
- Nó được che dấu để chỉ chứa các cột bắt buộc (0..8)
- Nhân với Số ma thuật, đẩy tất cả các bit gốc sang trái
- Byte ngoài cùng bên trái được dịch chuyển sang bên phải
Chọn Magic Number để chỉ sao chép các bit cần thiết và để các bit còn lại rơi vào vị trí không sử dụng/tràn số. Quá trình này trông như thế này (số là bit "ID", không phải chính số đó):
cột gốc: ...1.......2.......3.......4.......5.......6.......7.......8....
cột được căn chỉnh: 1.......2.......3.......4.......5.......6.......7.......8.......
nhân: 123456782345678.345678..45678...5678....678.....78......8.......
dịch chuyển sang phải:................................................................12345678
Nếu bạn thêm hằng số
Từ khóa, lắp ráp thực sự trở nên thực sự tốt:
lấy_cột:
.LFB7:
.cfi_startproc
di chuyển %esi, %ecx
movabsq $-9187201950435737472, %rax
%cl, %rdi
và q %rax, %rdi
movabsq $567382630219905, %rax
imulq %rax, %rdi
phía đông $56, %rdi
di chuyển %ed, %eax
Phải
Không có nhánh, không có dữ liệu bên ngoài, khoảng 0,4ns cho mỗi phép tính.
EDIT: Sử dụng giải pháp của NPE làm đường cơ sở mất khoảng 1/6 thời gian (nhanh nhất tiếp theo)
Tôi là một lập trình viên xuất sắc, rất giỏi!