Check if adjacent bits are set in the binary representation of a number

Given a number, check if adjacent bits are set in the binary representation of it.

Practice this problem

A naive solution is to consider every bit present in the number one by one and compare it with its previous bit. If the current bit is the same as the previous bit, we have found a pair whose adjacent bits are 1.

The expression n & (n << 1) or n & (n >> 1) returns true if n contains any pair whose adjacent bits are 1. For example,

00101101    &               (n)
01011010                    left shift n by 1
~~~~~~~~
00001000                    (n & (n << 1))

Following is the C++, Java, and Python program that demonstrates it:

C++

#include <iostream>

#include <bitset>

using namespace std;

// Returns true if adjacent bits are set in a binary representation of `n`

bool check(int n) {

return n & (n << 1);

}

int main()

{

int n = 67;

cout << n << " in binary is " << bitset<8>(n) << endl;

if (check(n)) {

cout << "Adjacent pair of set bits found";

}

else {

cout << "No adjacent pair of set bits found";

}

return 0;

}

Download Run Code

Output:

67 in binary is 01000011
Adjacent pair of set bits found

Java

class Main

{

// Returns true if adjacent bits are set in the binary representation of `n`

public static boolean check(int n) {

return (n & (n << 1)) != 0;

}

public static void main(String[] args)

{

int n = 67;

System.out.println(n + " in binary is " + Integer.toBinaryString(n));

if (check(n)) {

System.out.println("Adjacent pair of set bits found");

}

else {

System.out.println("No adjacent pair of set bits found");

}

Download Run Code

Output:

67 in binary is 1000011
Adjacent pair of set bits found

Python

# Returns true if adjacent bits are set in the binary representation of `n`

def check(n):

return (n & (n << 1)) != 0

if __name__ == '__main__':

n = 67

print(f'{n} in binary is {bin(n)}')

if check(n):

print('Adjacent pair of set bits found')

else:

print('No adjacent pair of set bits found')

Download Run Code

Output:

67 in binary is 0b1000011
Adjacent pair of set bits found

Also See:

Bit Hacks – Part 1 (Basic)
Bit Hacks – Part 2 (Playing with k’th bit)
Bit Hacks – Part 3 (Playing with the rightmost set bit of a number)
Bit Hacks – Part 4 (Playing with letters of the English alphabet)
Bit Hacks – Part 5 (Find the absolute value of an integer without branching)

Check if adjacent bits are set in the binary representation of a number

C++

Java

Python

Share this: