Check if a number has bits in an alternate pattern

8. Finding the most significant set bit (MSB):

We can quickly check if bits in a number are in an alternate pattern (like 101010).

Compute bitwise XOR (XOR denoted using ^) of n and (n >> 1). If n has an alternate pattern, then n ^ (n >> 1) operation will produce a number having all bits set.

Below is the implementation of the above approach.

C++

// function to check if all the bits
// are set or not in the binary
// representation of 'n'
static bool allBitsAreSet(int n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;

    // else all bits are not set
    return false;
}

// Function to check if a number
// has bits in alternate pattern
bool bitsAreInAltOrder(unsigned int n)
{
    unsigned int num = n ^ (n >> 1);

    // To check if all bits are set in 'num'
    return allBitsAreSet(num);
}

Java

/*package whatever //do not write package name here */
import java.io.*;

class GFG {

  // function to check if all the bits
  // are set or not in the binary
  // representation of 'n'
  public static boolean allBitsAreSet(long n)
  {

    // if true, then all bits are set
    if (((n + 1) & n) == 0)
      return true;

    // else all bits are not set
    return false;
  }

  // Function to check if a number
  // has bits in alternate pattern
  public static boolean bitsAreInAltOrder(long n)
  {
    long num = n ^ (n >> 1);

    // To check if all bits are set in 'num'
    return allBitsAreSet(num);
  }
  public static void main (String[] args) {

  }
}

// This code is contributed by akashish__

Python

# function to check if all the bits
# are set or not in the binary
# representation of 'n'
def allBitsAreSet(n):
  # if true, then all bits are set
  if (((n + 1) & n) == 0):
    return True

  # else all bits are not set
  return False

# Function to check if a number
# has bits in alternate pattern
def bitsAreInAltOrder(n):
  num = n ^ (n >> 1)

  # To check if all bits are set in 'num'
  return allBitsAreSet(num)


# This code is contributed by akashish__

using System;
public class GFG 
{

    // function to check if all the bits
    // are set or not in the binary
    // representation of 'n'
    public static bool allBitsAreSet(uint n)
    {
      
        // if true, then all bits are set
        if (((n + 1) & n) == 0)
            return true;

        // else all bits are not set
        return false;
    }

    // Function to check if a number
    // has bits in alternate pattern
    public static bool bitsAreInAltOrder(uint n)
    {
        uint num = n ^ (n >> 1);

        // To check if all bits are set in 'num'
        return allBitsAreSet(num);
    }

    static public void Main() {}
}

// This code is contributed by akashish__

Javascript

// function to check if all the bits
// are set or not in the binary
// representation of 'n'
function allBitsAreSet(n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;

    // else all bits are not set
    return false;
}

// Function to check if a number
// has bits in alternate pattern
function bitsAreInAltOrder(n)
{
    let num = n ^ (n >> 1);

    // To check if all bits are set in 'num'
    return allBitsAreSet(num);
}

// This code is contributed by akashish__

Time Complexity: O(1)
Auxiliary Space: O(1)

Refer check if a number has bits in alternate pattern for details.

DSA Self Paced Course

Bits manipulation (Important tactics)

Prerequisites: Bitwise operators in C, Bitwise Hacks for Competitive Programming, Bit Tricks for Competitive Programming

Table of Contents

Compute XOR from 1 to n (direct method)
Count of numbers (x) smaller than or equal to n such that n+x = n^x
How to know if a number is a power of 2?
Find XOR of all subsets of a set
Find the number of leading, trailing zeroes and number of 1’s
Convert binary code directly into an integer in C++
The Quickest way to swap two numbers
Simple approach to flip the bits of a number
Finding the most significant set bit (MSB)
Check if a number has bits in an alternate pattern

Check if a number has bits in an alternate pattern

Bits manipulation (Important tactics)

Similar Reads