Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bitwise

How do we check if a given number is an odious number?

Ravi

Overview

An odious number is a positive number whose count of set bits in its binary form is odd. All powers of 2 are odious numbers, as the number of set bits in them is 1.

For example, 7 is an odious number because the number of set bits in it is 3.

Given a number n, find whether it is an odious number or not.

Example 1:

  • Input: n = 5
  • Output: 5 is not an odious number.

Example 1:

  • Input: n = 2
  • Output: 2 is an odious number.

Solution

The solution is quite straightforward. The steps in figuring out the solution are as follows:

  1. Find the count of set bits in the given number.
  2. Check whether the result from step 1 is odd.

For step 1, refer to the How to find the number of set bits in an integer Answer.

For step 2, refer to the How to use bitwise operations to check if a number is even or odd Answer.

Example

def countSetBits(n):
    count = 0
    while n:
        n = n & (n - 1)
        count+=1
    return count

def isOdd(n):
    return (n & 1) == 1

n = 16
set_bit_count = countSetBits(n)
if isOdd(set_bit_count):
    print(n, "is an Odious number")
else:
    print(n, "is not an Odious number")

Explanation

  • Lines 1–6: We define a function called countSetBits that calculates the number of set bits in a given number.
  • Lines 8–9: We define a function called isOdd that states whether a given number is an odd number or not.
  • Line 11: We define the number to be checked as n.
  • Line 12: We invoke the countSetBits() function with n as the number and we get the number of set bits in n.
  • Lines 13–16: We check whether the result we got in line 18 is an odd number or not by invoking the isOdd function. Then, we print the result to the console.

RELATED TAGS

bitwise
RELATED COURSES

View all Courses

Keep Exploring