Check whether all the bits are unset in the given range or not
Given a non-negative number n and two values l and r. The problem is to check whether all the bits are unset or not in the range l to r in the binary representation of n.
Constraint: 1 <= l <= r <= number of bits in the binary representation of n.
Examples:
Input : n = 17, l = 2, r = 4 Output : Yes (17)10 = (10001)2 The bits in the range 2 to 4 are all unset. Input : n = 36, l = 3, r = 5 Output : No (36)10 = (100100)2 The bits in the range 3 to 5 are all not unset.
Approach: Following are the steps:
- Calculate num = ((1 << r) – 1) ^ ((1 << (l-1)) – 1). This will produce a number num having r number of bits and bits in the range l to r are the only set bits.
- Calculate new_num = n & num.
- If new_num == 0, return “Yes” (all bits are unset in the given range).
- Else return “No” (all bits are not unset in the given range).
C++
// C++ implementation to check whether all // the bits are unset in the given range // or not #include <bits/stdc++.h> using namespace std; // function to check whether all the bits // are unset in the given range or not string allBitsSetInTheGivenRange(unsigned int n, unsigned int l, unsigned int r) { // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // new number which will only have // one or more set bits in the range // l to r and nowhere else int new_num = n & num; // if new num is 0, then all bits // are unset in the given range if (new_num == 0) return "Yes" ; // else all bits are not unset return "No" ; } // Driver program to test above int main() { unsigned int n = 17; unsigned int l = 2, r = 4; cout << allBitsSetInTheGivenRange(n, l, r); return 0; } |
Java
// Java implementation to // check whether all the // bits are unset in the // given range or not import java.io.*; class GFG { // function to check whether // all the bits are unset in // the given range or not static String allBitsSetInTheGivenRange( int n, int l, int r) { // calculating a number 'num' // having 'r' number of bits // and bits in the range l to // r are the only set bits int num = (( 1 << r) - 1 ) ^ (( 1 << (l - 1 )) - 1 ); // new number which will // only have one or more // set bits in the range // l to r and nowhere else int new_num = n & num; // if new num is 0, then // all bits are unset in // the given range if (new_num == 0 ) return "Yes" ; // else all bits // are not unset return "No" ; } // Driver Code public static void main (String[] args) { int n = 17 ; int l = 2 ; int r = 4 ; System.out.println( allBitsSetInTheGivenRange(n, l, r)); } } // This code is contributed by akt_mit |
Python 3
# Python 3 implementation to check whether # all the bits are unset in the given range # or not # function to check whether all the bits # are unset in the given range or not def allBitsSetInTheGivenRange(n, l, r): # calculating a number 'num' having 'r' # number of bits and bits in the range l # to r are the only set bits num = (( 1 << r) - 1 ) ^ (( 1 << (l - 1 )) - 1 ) # new number which will only have # one or more set bits in the # range l to r and nowhere else new_num = n & num # if new num is 0, then all bits # are unset in the given range if (new_num = = 0 ): return "Yes" # else all bits are not unset return "No" # Driver Code if __name__ = = "__main__" : n = 17 l = 2 r = 4 print (allBitsSetInTheGivenRange(n, l, r)) # This code is contributed by ita_c |
C#
// C# implementation to // check whether all the // bits are unset in the // given range or not using System; public class GFG{ // function to check whether // all the bits are unset in // the given range or not static String allBitsSetInTheGivenRange( int n, int l, int r) { // calculating a number 'num' // having 'r' number of bits // and bits in the range l to // r are the only set bits int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // new number which will // only have one or more // set bits in the range // l to r and nowhere else int new_num = n & num; // if new num is 0, then // all bits are unset in // the given range if (new_num == 0) return "Yes" ; // else all bits // are not unset return "No" ; } // Driver Code static public void Main (){ int n = 17; int l = 2; int r = 4; Console.WriteLine( allBitsSetInTheGivenRange(n, l, r)); } } // This code is contributed by k_mit |
PHP
<?php // PHP implementation to check // whether all the bits are // unset in the given range // or not // function to check whether // all the bits are unset in // the given range or not function allBitsSetInTheGivenRange( $n , $l , $r ) { // calculating a number 'num' // having 'r' number of bits // and bits in the range l // to r are the only set bits $num = ((1 << $r ) - 1) ^ ((1 << ( $l - 1)) - 1); // new number which will // only have one or more // set bits in the range // l to r and nowhere else $new_num = $n & $num ; // if new num is 0, then // all bits are unset in // the given range if ( $new_num == 0) return "Yes" ; // else all bits // are not unset return "No" ; } // Driver Code $n = 17; $l = 2; $r = 4; echo allBitsSetInTheGivenRange( $n , $l , $r ); // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript implementation to check whether all // the bits are unset in the given range // or not // function to check whether all the bits // are unset in the given range or not function allBitsSetInTheGivenRange(n, l, r) { // calculating a number 'num' having 'r' // number of bits and bits in the range l // to r are the only set bits var num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // new number which will only have // one or more set bits in the range // l to r and nowhere else var new_num = n & num; // if new num is 0, then all bits // are unset in the given range if (new_num == 0) return "Yes" ; // else all bits are not unset return "No" ; } // Driver program to test above var n = 17; var l = 2, r = 4; document.write( allBitsSetInTheGivenRange(n, l, r)); </script> |
Output:
Yes
Time Complexity : O(1)
Auxiliary Space: O(1)
Contact Us