Làm thế nào tôi có thể thực hiện ý nghĩa logic với bitwise hoặc mã hiệu quả khác trong C?

Question

Tôi muốn thực hiện một phép toán logic hoạt động hiệu quả nhất có thể. Tôi cần bảng chân lý này:

p q p → q 
T T  T 
T F  F 
F T  T 
F F  T 

này, theo wikipedia được gọi là "logical implication"

Tôi đã dài cố gắng tìm hiểu làm thế nào để làm điều này với các hoạt động bitwise trong C mà không sử dụng điều kiện. Có lẽ ai đó đã có một số suy nghĩ về nó.

Cảm ơn

Answer 1

FYI, với gcc-4.3.3:

int foo(int a, int b) { return !a || b; } 
int bar(int a, int b) { return ~a | b; } 

Cung cấp (từ -d objdump):

0000000000000000 <foo>: 
    0: 85 ff     test %edi,%edi 
    2: 0f 94 c2    sete %dl 
    5: 85 f6     test %esi,%esi 
    7: 0f 95 c0    setne %al 
    a: 09 d0     or  %edx,%eax 
    c: 83 e0 01    and $0x1,%eax 
    f: c3      retq 

0000000000000010 <bar>: 
    10: f7 d7     not %edi 
    12: 09 fe     or  %edi,%esi 
    14: 89 f0     mov %esi,%eax 
    16: c3      retq 

Vì vậy, không có các chi nhánh, nhưng hướng dẫn gấp đôi nhiều.

@litb: Ok, đây là với _Bool:

0000000000000020 <baz>: 
    20: 40 84 ff    test %dil,%dil 
    23: b8 01 00 00 00   mov $0x1,%eax 
    28: 0f 45 c6    cmovne %esi,%eax 
    2b: c3      retq 

Vì vậy, sử dụng _Bool thay vì int là một ý tưởng tốt.

Answer 2

!p || q 

rất nhiều nhanh. nghiêm túc, đừng lo lắng về nó.

Answer 3

~p | q 

Đối với hình dung:

perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111' 
1011 

Trong mã chặt chẽ, điều này nên được nhanh hơn "! P || q" vì sau này có một chi nhánh, mà có thể gây ra một gian hàng trong CPU do lỗi dự đoán chi nhánh. Phiên bản bitwise là xác định và, như là một tiền thưởng, có thể làm 32 lần công việc nhiều hơn trong một số nguyên 32-bit so với phiên bản boolean!

Answer 4

Bạn có thể đọc lên trên deriving boolean expressions from truth Tables (cũng xem canonical form), về cách bạn có thể biểu diễn bất kỳ bảng chân lý nào dưới dạng kết hợp các hàm nguyên thủy hoặc hàm boolean.

Answer 5

Một giải pháp cho phép toán C (một chút bẩn, nhưng công trình):

((unsigned int)(p) <= (unsigned int)(q))

Nó hoạt động từ năm theo tiêu chuẩn C, 0 đại diện cho sai sự thật, và bất kỳ giá trị khác đúng (1 được trả về cho đúng bởi các toán tử boolean, loại int).

"bẩn" là tôi sử dụng booleans (p và q) làm số nguyên, mâu thuẫn với một số chính sách đánh máy mạnh (chẳng hạn như MISRA), tốt, đây là câu hỏi tối ưu hóa. Bạn luôn có thể #define dưới dạng macro để ẩn nội dung bẩn.

Đối với boolean phù hợp p và q (có hoặc là 0 hoặc 1 biểu diễn nhị phân) hoạt động. Nếu không, T->T có thể không sản xuất được T nếu p và q có các giá trị không đồng nhất tùy ý để biểu thị đúng sự thật.

Nếu bạn chỉ cần lưu trữ kết quả, vì Pentium II, có lệnh cmovcc (Chuyển điều kiện) (như được hiển thị trong câu trả lời của Derobert). Đối với boolean, tuy nhiên ngay cả 386 có một tùy chọn không có nhánh, lệnh setcc, trong đó tạo ra 0 hoặc 1 trong vị trí byte kết quả (đăng ký byte hoặc bộ nhớ). Bạn cũng có thể thấy rằng trong câu trả lời của Derobert, và giải pháp này cũng biên dịch thành một kết quả liên quan đến một setcc (setbe: Đặt nếu dưới hoặc bằng nhau).

Derobert và Chris Dolan ~p | q biến thể phải là nhanh nhất để xử lý số lượng lớn dữ liệu vì nó có thể xử lý ý nghĩa trên tất cả các bit của p và q riêng lẻ.

Lưu ý rằng thậm chí không giải pháp !p || q biên dịch thành mã phân nhánh trên x86: nó sử dụng hướng dẫn setcc. Đó là giải pháp tốt nhất nếu p hoặc q có thể chứa các giá trị không đồng nhất tùy ý thể hiện đúng sự thật. Nếu bạn sử dụng loại _Bool, nó sẽ tạo ra rất ít hướng dẫn.

tôi có những nhân vật sau khi biên dịch cho x86: Kết quả

__attribute__((fastcall)) int imp1(int a, int b) 
{ 
return ((unsigned int)(a) <= (unsigned int)(b)); 
} 

__attribute__((fastcall)) int imp2(int a, int b) 
{ 
return (!a || b); 
} 

__attribute__((fastcall)) _Bool imp3(_Bool a, _Bool b) 
{ 
return (!a || b); 
} 

__attribute__((fastcall)) int imp4(int a, int b) 
{ 
return (~a | b); 
} 

hội:

00000000 <imp1>: 
    0: 31 c0     xor %eax,%eax 
    2: 39 d1     cmp %edx,%ecx 
    4: 0f 96 c0    setbe %al 
    7: c3      ret  

00000010 <imp2>: 
    10: 85 d2     test %edx,%edx 
    12: 0f 95 c0    setne %al 
    15: 85 c9     test %ecx,%ecx 
    17: 0f 94 c2    sete %dl 
    1a: 09 d0     or  %edx,%eax 
    1c: 0f b6 c0    movzbl %al,%eax 
    1f: c3      ret  

00000020 <imp3>: 
    20: 89 c8     mov %ecx,%eax 
    22: 83 f0 01    xor $0x1,%eax 
    25: 09 d0     or  %edx,%eax 
    27: c3      ret  

00000030 <imp4>: 
    30: 89 d0     mov %edx,%eax 
    32: f7 d1     not %ecx 
    34: 09 c8     or  %ecx,%eax 
    36: c3      ret  

Khi sử dụng các loại _Bool, trình biên dịch khai thác rõ ràng rằng nó chỉ có hai giá trị có thể (0 cho sai và 1 cho đúng), tạo ra một kết quả rất giống với giải pháp ~a | b (sự khác biệt duy nhất là sau này thực hiện một bổ sung trên tất cả các bit thay vì chỉ bit thấp nhất).

Biên dịch cho 64 bit chỉ cho kết quả tương tự.

Dù sao thì rõ ràng, phương pháp này thực sự không quan trọng từ điểm tránh sản xuất điều kiện.