Check if a number has bits in an alternate pattern
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.
// 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);
}
/*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__
# 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__
// 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.
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