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. The bits are numbered from right to left, i.e., the least significant bit is considered to be at first position.
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 = 39, l = 4, r = 6
Output : No
(39)10 = (100111)2
The bits in the range 4 to 6 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 notbool 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 could only have one or more // set bits in the range l to r and nowhere else int new_num = n & num; // if true, then all bits are unset // in the given range if (new_num == 0) return true; // else all bits are not unset // in the given range return false;}// Driver program to test aboveint main(){ unsigned int n = 17; unsigned int l = 2, r = 4; if (allBitsSetInTheGivenRange(n, l, r)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation to check // whether all the bits are // unset in the given range or notclass GFG{ // function to check whether // all the bits are unset in// the given range or notstatic boolean 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 could only // have one or more set bits in // the range l to r and nowhere else int new_num = n & num; // if true, then all bits are // unset in the given range if (new_num == 0) return true; // else all bits are not // unset in the given range return false;}// Driver Codepublic static void main(String[] args){ int n = 17; int l = 2, r = 4; if (allBitsSetInTheGivenRange(n, l, r)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed// by Smitha |
Python3
# Python3 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 notdef 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 could only # have one or more set bits in # the range l to r and nowhere else new_num = n & num # if true, then all bits are # unset in the given range if (new_num == 0): return True # else all bits are not # unset in the given range return false# Driver Coden = 17l = 2r = 4if (allBitsSetInTheGivenRange(n, l, r)): print("Yes")else: print("No")# This code is contributed # by Smitha |
C#
// C# implementation to check // whether all the bits are // unset in the given range or notusing System;class GFG{ // function to check whether // all the bits are unset in// the given range or notstatic bool 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 could // only have one or more // set bits in the range // l to r and nowhere else int new_num = n & num; // if true, then all // bits are unset // in the given range if (new_num == 0) return true; // else all bits are not // unset in the given range return false;}// Driver Codepublic static void Main(){ int n = 17; int l = 2, r = 4; if (allBitsSetInTheGivenRange(n, l, r)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed // by Smitha |
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 notfunction 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 could only // have one or more set bits in // the range l to r and nowhere else $new_num = $n & $num; // if true, then all bits are // unset in the given range if ($new_num == 0) return true; // else all bits are not unset // in the given range return false;}// Driver Code$n = 17;$l = 2;$r = 4;if (allBitsSetInTheGivenRange($n, $l, $r)) echo "Yes";else echo "No"; // This code is contributed by Smitha?> |
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 notfunction 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 let num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // new number which could only have one or more // set bits in the range l to r and nowhere else let new_num = n & num; // if true, then all bits are unset // in the given range if (new_num == 0) return true; // else all bits are not unset // in the given range return false;}// Driver program to test above let n = 17; let l = 2, r = 4; if (allBitsSetInTheGivenRange(n, l, r)) document.write("Yes"); else document.write("No");</script> |
Output:
Yes
Time complexity: O(1) since constant bit operations are done
Auxiliary space: O(1)
Share your thoughts in the comments
