Abominable numbers

A number is considered odd if it has an odd number of ones in its binary expansion. The first 10 odd numbers are 1,2,4,7,10,11,13,14,16,19,21. Interestingly, all powers of 2 are odd numbers because they only have 1 bit set.

The following article discusses in detail two methods of determining whether a number is a hateful number.

Problem Statement

The purpose of this question is to check if the given number is an abominable number, i.e. it is a positive number with an odd number of set bits in its binary expansion.

Disgusting digital examples

Input: 34

Output: Non-Odious Number

illustrate

The binary representation of

34 is 10010.

Set number of digits = 2.

Since the number of 1's is an even number, 34 is not a terrible number.

Input: 1024

Output: Odious Number

illustrate

The binary representation of

1024 is 10000000000.

Set number of digits = 1.

Since 1024 is a power of 2, there is only 1 setting bit. So it's a scary number.

Input: 53

Output: Non-Odious Number

illustrate

(53)₁₀ = (110101)₂

Set number of digits = 4.

Therefore, it is not an abominable number.

solution

In order to determine whether a number is hateful, we must know whether the number of digits set is an odd or even number. The main task here is to count the number of digits set in the binary expansion of a number. The following technique can be used to count the number of digits and then check whether the result is odd or even.

The Chinese translation of

Naive Approach

is:

Naive Approach

• Use the loop and right shift operators to iterate through all the digits of the number one by one.

• If the bit value is 1, increase the count by one.

• Check whether the final value of count is odd or even.

• Show answer.

pseudocode

Function no_of_set_bits()

• Initialization count = 0

• When (n > 0)

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

• Return count

Function is_odious()

• If (count is an odd number)

return true

• other

Return error

Function main()

• Initialization n

• Function call no_of_set_bits()

• Call function is_odious()

• Print output

Example: C program

This program checks whether a number is offensive. It checks the rightmost bit in each iteration of the loop by shifting the value to the right by 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 and space analysis

Time complexity: O(log(n)), because binary expansion of n requires log2n bits, we check all bits to check which bits are set.

Space complexity: O(1), because no additional space is used.

Brian Kernighan’s Algorithmic Method

This algorithm can be used to calculate a set number of digits in a number in a more efficient way. The function is_odious() can then be used to determine whether the number is offensive.

The basic principle of this method is to repeatedly clear the rightmost set bit of the number while keeping track of how many iterations are needed to reach zero. The steps involved are -

• Initialize count to 0

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

• The count is incremented with each loop iteration.

• Check if the final count is odd.

• Show results.

Example

Suppose the number is 10. The binary expansion of 10 is 1010. It can be observed that it has 2 setting 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 settings = 2.

pseudocode

Function no_of_set_bits()

• Initialization count = 0

• When (n > 0)

n = n & (n-1)

Increase count

• Return count

Function is_odious()

Same as previous method

Function main()

Same as previous method

Example: C program

This program calculates the number of set bits by counting the number of iterations required to unset all bits. To cancel bits, we perform a bitwise AND operation on n and n-1. This is because the binary representation of n-1 flips n's rightmost set bit and all the bits that follow it.

#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

Space-time analysis

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

Space Complexity - O(1) because no extra space is used.

Compare the above methods

While the first approach is fairly easy to understand, it requires log(n) iterations to produce the final result. The second method, on the other hand, uses log(x) iteration, where x is the number of digits set in the binary expansion of the number. Therefore, it improves performance.

in conclusion

This article discusses two ways to check whether a number is objectionable. It also provides us with the concept of the method, examples, algorithms used, C program solutions, and complexity analysis of each method. It also compared the two methods to determine which was more effective.

The above is the detailed content of Abominable numbers. For more information, please follow other related articles on the PHP Chinese website!