Cách sáng tạo để kiểm tra xem số chỉ có một bit trên ký tự int

Question

Tôi đang tìm một cách sáng tạo để kiểm tra xem một số chỉ có một bit trên một int đã ký.

Tôi biết rõ rằng tôi có thể thực hiện một vòng lặp với bộ đếm, một số phân chia mô-đun và thay đổi một chút. Nhưng tôi tò mò nếu có một cách tốt hơn vì chúng tôi chỉ tìm kiếm một chút để được trên.

bool HasOnlyOneBit (int numb) 
{ 
    //return true if numb has only one bit (I.E. is equal to 1, 2, 4, 8, 16... Int.MinValue) 
} 

Answer 1

return x == (x & -x); 

Câu trả lời này làm việc vì ký hiệu bổ sung cách hai được thiết kế.

Trước tiên, ví dụ. Giả sử chúng ta có số nguyên được ký 8 bit.

00010000 = 16 
11110000 = -16 

Bitwise và sẽ cung cấp cho bạn 00010000 kết quả, bằng với giá trị ban đầu của bạn! Lý do mà công trình này là vì khi phủ nhận trong phần bổ sung của 2, đầu tiên đảo ngược tất cả các bit, sau đó thêm 1. Bạn sẽ có một loạt các số không và một bó mang cho đến khi một cái rơi vào vị trí. Các bitwise và sau đó kiểm tra nếu chúng ta có bit được thiết lập đúng.

Trong trường hợp của một số đó không phải là một sức mạnh của hai:

00101010 = 42 
& 11010110 = -42 
---------- 
    00000010 != 42 

Kết quả của bạn vẫn sẽ chỉ có một chút duy nhất, nhưng nó sẽ không phù hợp với giá trị ban đầu. Do đó, giá trị ban đầu của bạn có nhiều bit được đặt.

Lưu ý: Kỹ thuật này trả về giá trị đúng cho 0, có thể hoặc không mong muốn.

Answer 2

Tôi khuyên bạn nên xem trang Bit Twiddling Hacks và chọn tùy chọn phù hợp nhất trong "Determining if an integer is a power of 2" hoặc "Counting bits set".

Answer 3

Đây là vấn đề nổi tiếng

(x & x-1) == 0 

Sức mạnh của 2 từ Wiki: here

64 = 01000000 (x) 
63 = 00111111 (x-1) 
______________ 
& = 00000000 == 0 
______________ 

Trường hợp khi một số bit khác là ON

18 = 00010010 (x) 
17 = 00010001 (x-1) 
______________ 
& = 00010000 != 0 
______________ 

Answer 4

Hãy đăng nhập để căn 2 số của bạn, nếu đó là số nguyên, số của bạn chỉ có 1 1 bit. Không chắc chắn rằng tôi nghĩ rằng điều này là tốt hơn so với bất kỳ tùy chọn bị loại trừ nào của bạn.

Answer 5

return (x && ((x & x-1) == 0))

Answer 6

return (x && (0x8000000000000000ULL % x)); 

Đây là một việc đơn giản hóa các đoạn mã sau:

if (x == 0) { 
    return false; 
} else if (0x8000000000000000ULL % x) { 
    return false; 
} else { 
    return true; 
} 

Giải thích: 0x8000000000000000 là "chỉ có 1 chút" giá trị cao nhất cho một thanh ghi 64 bit. Chỉ một bộ phận bằng một giá trị "1 bit duy nhất" khác sẽ dẫn đến phần còn lại.