Hoán đổi hai bit với một thao tác đơn trong C?

Question

Hãy nói rằng tôi có một byte với sáu giá trị chưa biết:

???1?0?? 

và tôi muốn trao đổi bit 2 và 4 (mà không thay đổi bất kỳ ? giá trị):

???0?1?? 

Nhưng làm thế nào tôi có thể làm điều này trong một hoạt động trong C?

Tôi đang thực hiện thao tác này hàng nghìn lần mỗi giây trên vi điều khiển để hiệu suất là ưu tiên hàng đầu.

Sẽ là tốt để "chuyển đổi" các bit này. Mặc dù điều này là không giống như trao đổi các bit, toggling sẽ làm việc tốt cho mục đích của tôi.

Answer 1

Hãy thử:

x ^= 0x14; 

Đó Toggles cả hai bit. Đó là một chút không rõ ràng trong câu hỏi như bạn lần đầu tiên đề cập đến trao đổi và sau đó đưa ra một ví dụ chuyển đổi. Dù sao, để trao đổi các bit:

x = precomputed_lookup [x]; 

nơi precomputed_lookup là một mảng 256 byte, có thể là cách nhanh nhất, nó phụ thuộc vào tốc độ bộ nhớ tương đối so với tốc độ xử lý. Nếu không, đó là:

x = (x & ~0x14) | ((x & 0x10) >> 2) | ((x & 0x04) << 2); 

EDIT: Một số thông tin khác về các bit chuyển đổi.

Khi bạn xor (^) hai giá trị số nguyên với nhau, xor được thực hiện ở cấp độ bit, như thế này:

for each (bit in value 1 and value 2) 
    result bit = value 1 bit xor value 2 bit 

để bit 0 của giá trị đầu tiên được xor'ed với bit 0 của giá trị thứ hai, bit 1 với bit 1 và vân vân. Thao tác xor không ảnh hưởng đến các bit khác trong giá trị. Trong thực tế, nó là một bit xor song song trên nhiều bit.

Nhìn vào bảng sự thật cho xor, bạn sẽ thấy rằng xor'ing một chút với giá trị '1' hiệu quả chuyển đổi bit.

a b a^b 
0 0 0 
0 1 1 
1 0 1 
1 1 0 

Vì vậy, để chuyển các bit 1 và 3, hãy viết một số nhị phân với một trong những nơi bạn muốn các bit để chuyển đổi và một số không, nơi bạn muốn để lại giá trị không thay đổi:

00001010 

convert tới hex: 0x0a. Bạn có thể chuyển đổi nhiều bit như bạn muốn:

0x39 = 00111001 

sẽ chuyển bit 0, 3, 4 và 5

Answer 2

Bạn không thể "hoán đổi" hai bit (tức là các bit thay đổi nơi, không giá trị) trong một hướng dẫn đơn sử dụng bit-fiddling.

Cách tiếp cận tối ưu nếu bạn muốn thực sự trao đổi chúng có thể là bảng tra cứu. Điều này đúng với nhiều biến đổi 'khó xử'.

BYTE lookup[256] = {/* left this to your imagination */}; 

for (/*all my data values */) 
    newValue = lookup[oldValue]; 

Answer 3

Phương pháp sau KHÔNG PHẢI là một hướng dẫn đơn C, nó chỉ là một phương pháp không quan trọng khác. Phương pháp đã được đơn giản hóa từ Swapping individual bits with XOR.

Như đã nêu trong Roddy's answer, bảng tra cứu sẽ là tốt nhất. Tôi chỉ đề nghị điều này trong trường hợp bạn không muốn sử dụng nó. Điều này thực sự sẽ trao đổi bit cũng, không chỉ chuyển đổi (có nghĩa là, bất cứ điều gì là trong bit 2 sẽ được trong 4 và ngược lại).

• b: giá trị ban đầu của bạn - ??? 1? 0 ?? ví dụ
• x: chỉ cần một temp

• r: kết quả

  x = ((b >> 2)^(b >> 4)) & 0x01
  r = b^((x < < 2) | (x < < 4))

giải thích nhanh: có được hai bit bạn muốn xem xét và XOR chúng, lưu trữ các giá trị cho x. Bằng cách dịch chuyển giá trị này về bit 2 và 4 (và OR'ing cùng nhau) bạn sẽ nhận được một mặt nạ khi XORed quay lại với b sẽ hoán đổi hai bit gốc của bạn. Bảng dưới đây cho thấy tất cả các trường hợp có thể xảy ra.

bit2: 0 1 0 1 
bit4: 0 0 1 1 
x : 0 1 1 0 <-- Low bit of x only in this case 
r2 : 0 0 1 1 
r4 : 0 1 0 1 

Tôi đã không kiểm tra đầy đủ điều này, nhưng đối với một số trường hợp, tôi đã thử nhanh nó dường như hoạt động.

Answer 4

Hàm dưới đây sẽ hoán đổi bit 2 và 4. Bạn có thể sử dụng để precompute một bảng tra cứu, nếu cần thiết (để trao đổi mà sẽ trở thành một hoạt động đơn lẻ):

unsigned char swap24(unsigned char bytein) { 
    unsigned char mask2 = (bytein & 0x04) << 2; 
    unsigned char mask4 = (bytein & 0x10) >> 2; 
    unsigned char mask = mask2 | mask4 ; 
    return (bytein & 0xeb) | mask; 
} 

tôi đã viết mỗi hoạt động trên riêng để làm cho nó rõ ràng hơn.

Answer 5

này có thể không được tối ưu hóa, nhưng nó cũng làm việc:

unsigned char bit_swap(unsigned char n, unsigned char pos1, unsigned char pos2) 
{ 
    unsigned char mask1 = 0x01 << pos1; 
    unsigned char mask2 = 0x01 << pos2; 
    if (!((n & mask1) != (n & mask2))) 
     n ^= (mask1 | mask2); 
    return n; 
} 

Answer 6

Giả sử giá trị của bạn là x tức là, x = ??? 1 0 ??

Hai bit có thể được toggled bởi hoạt động này:

x = x^((1<<2) | (1<<4)); 

Answer 7

#include<stdio.h> 

void printb(char x) { 
    int i; 
    for(i =7;i>=0;i--) 
     printf("%d",(1 & (x >> i))); 
    printf("\n"); 
} 

int swapb(char c, int p, int q) { 
    if(!((c & (1 << p)) >> p)^((c & (1 << q)) >> q)) 
     printf("bits are not same will not be swaped\n"); 
    else { 
     c = c^(1 << p); 
     c = c^(1 << q); 
    } 
    return c; 
} 

int main() 
{ 
    char c = 10; 
    printb(c); 
    c = swapb(c, 3, 1); 
    printb(c); 
    return 0; 
} 

Answer 8

void swap_bits(uint32_t& n, int a, int b) { 
    bool r = (n & (1 << a)) != 0; 
    bool s = (n & (1 << b)) != 0; 

    if(r != s) { 
     if(r) { 
      n |= (1 << b); 
      n &= ~(1 << a); 
     } 
     else { 
      n &= ~(1 << b); 
      n |= (1 << a); 
     } 
    } 
} 

n là số nguyên bạn muốn được đổi chỗ ở, a và b là các vị trí (chỉ số) của các bit bạn muốn được đổi chỗ, đếm từ bit ít quan trọng hơn và bắt đầu từ số không.

Sử dụng ví dụ của bạn (n = ???1?0??), bạn muốn gọi hàm như sau:

swap_bits(n, 2, 4); 

Lý: bạn chỉ cần trao đổi các bit nếu chúng khác nhau (đó là lý do tại sao r != s). Trong trường hợp này, một trong số đó là 1 và số kia là 0.Sau đó, chỉ cần thông báo bạn muốn thực hiện chính xác một hoạt động bit thiết lập hoạt động và một hoạt động bit rõ ràng.