可憎的数字

如果一个数字在其二进制展开中有奇数个1，则被认为是奇异数。前10个奇异数是1,2,4,7,10,11,13,14,16,19,21。有趣的是，所有2的幂都是奇异数，因为它们只有1个位被设置。

The following article discusses 2 approaches in detail to find whether a number is an odious number or not.

Problem Statement

This problem aims to check whether the given number is an odious number i.e. it is a positive number with an odd number of set bits in its binary expansion.

Examples of Odious Number

Input: 34

Output: Non-Odious Number

Explanation

34的二进制表示是10010。

Number of set bits = 2.

由于1的数量是偶数，34不是一个可怕的数字。

Input: 1024

Output: Odious Number

Explanation

Binary representation of 1024 is 10000000000.

Number of set bits = 1.

由于1024是2的幂，所以只有1个设置位。因此它是一个可怕的数字。

Input: 53

Output: Non-Odious Number

Explanation

(53)₁₀ = (110101)₂

Number of set bits = 4.

因此，它不是一个可憎的数字。

Solution Approach

In order to determine if a number is odious or not, we must know whether the number of set bits is odd or even. The main task here is to count the number of set bits in the binary expansion of the number. The following techniques can be employed to count the number of bits and then check if the result is odd or even.

Naive Approach

的中文翻译为：

天真的方法

• Go through all the bits of the number, one by one, using a loop and a right shift operator.

• 如果位值为1，则将计数增加一。

• 检查 count 的最终值是奇数还是偶数。

• 显示答案。

伪代码

Function no_of_set_bits()

• 初始化计数 = 0

• while (n > 0)

if ((n & 1) > 0)
   Increment count
Right Shift n

• return count

Function is_odious()

• 如果 (count 是奇数)

return true

• else

return false

Function main()

• 初始化 n

• Function call no_of_set_bits()

• 调用函数 is_odious()

• Print output

Example: C++ Program

The program checks whether a number is odious or not. It examines the right most bit in every iteration of the loop by right shifting the value of n at the end of each iteration in the function no_of_set_bits().

#include<iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next bit
      n = n >> 1;
   }
   return count;
}
// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n);
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Output

27 is Non-Odious Number

时间和空间的分析

Time Complexity: O(log(n)), since binary expansion of n takes log2n bits and we examine all the bits to check for set bits.

Space Complexity: O(1) , as no extra space is used.

Brian Kernighan’s Algorithm Approach

This algorithm can be employed to count the number of set bits for a number in a more efficient way. Function is_odious() can then be used to determine whether the number is odious.

The fundamental principle of this approach is to repeatedly clear the number's rightmost set bit while keeping track of how many iterations are needed to get to zero. The steps involved are −

• 将计数初始化为0

• While the number is greater than zero, perform bitwise & between the number and its 2’s complement to unset the rightmost set bit.

• Increment count with each iteration of the loop.

• Check whether the final count is odd.

• Display the result.

Example

Let the number be 10. The binary expansion of 10 is 1010. It can be observed that it has 2 set bits.

Loop iteration 1 −

n = 10
n & (n-1) =  10 & 9
1010   (n)
1001   (n - 1)
1000   (n = 8)

Loop iteration 2 −

n = 8
n & (n-1) = 8 & 7
1000    (n)
0111	(n-1)
0       (n = 0) 

Number of iterations = Number of set bits = 2.

伪代码

Function no_of_set_bits()

• 初始化计数 = 0

• while (n > 0)

n = n & (n-1)

Increment count

• return count

Function is_odious()

Same as in the previous approach

Function main()

Same as in the previous approach

Example: C++ Program

这个程序通过计算需要取消所有设置位所需的迭代次数来计算设置位的数量。为了取消位，我们对n和n-1执行位与操作。这是因为n-1的二进制表示会翻转n的最右边的设置位以及其后面的所有位。

#include<iostream>
using namespace std;
// this function counts the number of set bits by unsetting the rightmost set bit using a while loop till n > 0.
// it performs logical & operation between n and n - 1 to unset the rightmost set bit.
// count is incremented in every iteration
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
      // update the value of n to unset the current rightmost set bit
      n = n & (n - 1);
      count++;
   }
   return count;
}

// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n); // function call
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Output

27 is Non-Odious Number

Time and Space Analysis

Time Complexity − O(log(x)), where x is the number of set bits in the number. If there is only 1 set bit, the loop will run once.

Space Complexity − O(1) , as no extra space is used.

比较上述方法

While the first approach is fairly easy to understand, it takes log(n) iterations to produce the final result. The second approach, on the other hand, takes log(x) iterations, where x is the number of set bits in the binary expansion of the number. Hence, it improves the performance.

结论

This article discusses two approaches to check whether a number is odious. It also provides us with the concept of the approach, examples, algorithm used, C++ program solution as well as the complexity analysis of each method. It also draws comparison between the two approaches to figure out which one is more efficient.