Check if a number has two adjacent set bits
Given a number you have to check whether there is pair of adjacent set bit or not.
Examples :
Input : N = 67 Output : Yes There is a pair of adjacent set bit The binary representation is 100011 Input : N = 5 Output : No
A simple solution is to traverse all bits. For every set bit, check if next bit is also set.
An efficient solution is to shift number by 1 and then do bitwise AND. If bitwise AND is non-zero then there are two adjacent set bits. Else not.
C++
// CPP program to check // if there are two // adjacent set bits. #include <iostream> using namespace std; bool adjacentSet( int n) { return (n & (n >> 1)); } // Driver Code int main() { int n = 3; adjacentSet(n) ? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check // if there are two // adjacent set bits. class GFG { static boolean adjacentSet( int n) { int x = (n & (n >> 1 )); if (x > 0 ) return true ; else return false ; } // Driver code public static void main(String args[]) { int n = 3 ; if (adjacentSet(n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Sam007. |
Python3
# Python 3 program to check if there # are two adjacent set bits. def adjacentSet(n): return (n & (n >> 1 )) # Driver Code if __name__ = = '__main__' : n = 3 if (adjacentSet(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Shashank_Sharma |
C#
// C# program to check // if there are two // adjacent set bits. using System; class GFG { static bool adjacentSet( int n) { int x = (n & (n >> 1)); if (x > 0) return true ; else return false ; } // Driver code public static void Main () { int n = 3; if (adjacentSet(n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by Sam007. |
php
<?php // PHP program to check // if there are two // adjacent set bits. function adjacentSet( $n ) { return ( $n & ( $n >> 1)); } // Driver Code $n = 3; adjacentSet( $n ) ? print ( "Yes" ) : print ( "No" ); // This code is contributed by Sam007. ?> |
Javascript
<script> // Javascript program to check // if there are two // adjacent set bits. function adjacentSet(n) { let x = (n & (n >> 1)); if (x > 0) return true ; else return false ; } // driver program let n = 3; if (adjacentSet(n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output :
Yes
Time Complexity : O(1)
Auxiliary Space : O(1)