Hoán đổi từng cặp bit theo byte

Question

Đây là câu hỏi được hỏi bởi một đại diện của NVIDIA tại hội chợ nghề nghiệp:

Viết mã nhỏ, hiệu quả để hoán đổi từng cặp bit trong một byte; ví dụ: 10 11 01 10 phải trở thành 01 11 10 01.

Có cách nào hiệu quả hơn để thực hiện việc này không bằng cách thực hiện vòng lặp for thông qua mọi chỉ mục khác? Mã của tôi là nhỏ, nhưng tôi không thể nghĩ có bao nhiêu "hiệu quả" này có thể có thể nhận được hơn một vòng lặp ... Tôi đoán có thể có một cách để sử dụng XOR để tránh một vòng lặp, nhưng tôi không thể tìm ra.

Cảm ơn!

Answer 1

Bạn có thể sử dụng bảng tra cứu 256 mục nhập.

Cách khác, ((x & 0x55) << 1) | ((x & 0xAA) >> 1).

Answer 2

Tra cứu bảng (trừ khi có một số giải pháp cụ thể về NVIDA mà anh đang tìm kiếm).

Answer 3

Something như thế này nên làm việc

(i >> 1) & 01010101 + (i << 1) & 10101010 

i >> 1 thay đổi tất cả mọi thứ bằng 1 chút về bên phải, và & 01010101 lá chỉ bit tại thậm chí vị trí.
Giao dịch phần thứ hai với các vị trí bit lẻ trong cùng một fasion.

Không chắc chắn hiệu quả của nó.

Answer 4

Vì chỉ có 256 kết hợp có thể trong một byte, điều này có vẻ giống như một ứng cử viên tốt cho việc sử dụng giải pháp dựa trên bảng tra cứu cho bất kỳ thời điểm nào khi tốc độ thực hiện liên tục quan trọng hơn so với thời gian tính trước và/hoặc sử dụng bộ nhớ tổng.

Ví dụ:

lookupTable[00000000] = 00000000 
lookupTable[00000001] = 00000010 
lookupTable[00000010] = 00000001 
... 

Answer 5

Nếu không có bảng tra cứu (hoặc để tạo điều ở nơi đầu tiên), bạn cũng có thể:

• chuyển trái và AND với mặt nạ trái-bit (10101010)
• shift right và AND với mặt nạ bit phải (01010101)
• HOẶC kết quả với nhau.

chuyển trái là 01 10 11 00 đeo mặt nạ với 10101010 ban cho chúng ta 00 10 10 00

chuyển quyền (bản gốc) là đeo mặt nạ với 01.010.101 cho chúng ta 01 01 00 01

HOẶC kết quả của chúng tôi cùng nhau

Vì vậy, trong C hoặc C++ bạn có thể làm

unsigned char bitswap(unsigned char uch) 
{ 
    return ((uch<<1) & 0xAA) | (uch>>1) & 0x55); 
} 

Chỉ cần chạy mà cho tất cả các giá trị từ 0x00 đến 0xFF (đảm bảo vòng lặp của bạn chấm dứt!) Để tạo ra "bảng" của bạn.

Answer 6

Đối với 32-bit interger trong java ..

public int swapOddEvenbits(int x) 
{ 
    return ( ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1)); 

} 

Nếu bạn đang làm việc với 64-bit, bạn sẽ cần phải thay đổi mặt nạ ..