Skip to main content

Check if all bits of a number is active

The problem at hand involves determining whether all bits in a given number are set to 1 (active) or not. In binary representation, a set bit is denoted by 1 and an unset bit by 0. The task is to devise a method to quickly ascertain whether all bits in the binary representation of a number are set to 1.

Problem Statement and Description

Given an integer num, the goal is to determine whether all its bits are set to 1. In other words, we need to check if the binary representation of the number consists of all 1s. This task can be accomplished using bitwise operations and without actually converting the number to its binary representation.

Example

Let's take an example to illustrate the problem. Consider the integer -1. In binary, -1 is represented as 11111111 (assuming 8-bit representation). All bits are set to 1. So, the expected output for this example should be "Yes".

Another example is -4. In binary, -4 is represented as 11111100. Not all bits are set to 1. Thus, the expected output for this example should be "No".

Idea to Solve the Problem

Check whether all bits are set in given number

The key idea to solve this problem lies in understanding bitwise operations. Specifically, we can use the bitwise AND operation to check whether all bits are set to 1. The expression ((num + 1) & num) == 0 can be employed to determine whether all bits are active.

Pseudocode

Here's the pseudocode for the algorithm:

function isActiveBits(num):
    if num != 0 and ((num + 1) & num) == 0:
        print "Yes"
    else:
        print "No"

Algorithm Explanation

  1. Start by checking if the given number num is not equal to 0.
  2. If num is not zero, apply the bitwise AND operation between (num + 1) and num.
  3. If the result of the bitwise AND operation is equal to 0, then it indicates that all bits are set to 1 in the binary representation of the number. In this case, print "Yes".
  4. Otherwise, if the result is not equal to 0, then there is at least one unset bit. In this case, print "No".

Code Solution

Resultant Output Explanation

For the given code and the provided test cases, let's break down the output:

  1. For the number -1:

    • Binary representation: 11111111
    • The expression (0b11111111 + 1) & 0b11111111 results in 0b100000000 & 0b11111111, which is 0.
    • The output is "Yes" because all bits are set.
  2. For the number -4:

    • Binary representation: 11111100
    • The expression (0b11111100 + 1) & 0b11111100 results in 0b100000101 & 0b11111100, which is not 0.
    • The output is "No" because not all bits are set.
  3. For the number 15:

    • Binary representation: 00001111
    • The expression (0b00001111 + 1) & 0b00001111 results in 0b00010000 & 0b00001111, which is not 0.
    • The output is "Yes" because all bits are set.
  4. For the number 100:

    • Binary representation: 01100100
    • The expression (0b01100100 + 1) & 0b01100100 results in 0b01100101 & 0b01100100, which is not 0.
    • The output is "No" because not all bits are set.

Time Complexity

The time complexity of the algorithm is constant (O(1)) since it involves a fixed number of operations regardless of the input size. It relies on basic bitwise operations that can be executed efficiently by the hardware.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment