Previous smaller integer having one less number of set bits
Given a positive integer ‘n’ having ‘x’ number of set bits in its binary representation. The problem is to find the previous smaller integer(greatest integer smaller than n), having (x-1) number of set bits in its binary representation.
Note: 1 <= n
Examples :
Input : 8 Output : 0 (8)10 = (1000)2 is having 1 set bit. (0)10 = (0)2 is having 0 set bit and is the previous smaller. Input : 25 Output : 24
The following are the steps:
C++
// C++ implementation to find the previous // smaller integer with one less number of // set bits #include<bits/stdc++.h> using namespace std; // function to find the position of // rightmost set bit. int getFirstSetBitPos( int n) { return log2(n & -n) + 1; } // function to find the previous smaller // integer int previousSmallerInteger( int n) { // position of rightmost set bit of n int pos = getFirstSetBitPos(n); // turn off or unset the bit at // position 'pos' return (n & ~(1 << (pos - 1))); } // Driver program int main() { int n = 25; cout << previousSmallerInteger(n); return 0; } |
Java
// Java implementation to find the previous // smaller integer with one less number of // set bits class GFG { // function to find the position of // rightmost set bit. static int getFirstSetBitPos( int n) { return ( int )(Math.log(n & -n) / Math.log( 2 )) + 1 ; } // function to find the previous smaller // integer static int previousSmallerInteger( int n) { // position of rightmost set bit of n int pos = getFirstSetBitPos(n); // turn off or unset the bit at // position 'pos' return (n & ~( 1 << (pos - 1 ))); } // Driver code public static void main(String[] args) { int n = 25 ; System.out.print( "Previous smaller Integer =" + previousSmallerInteger(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 implementation to find # the previous smaller integer with # one less number of set bits import math # Function to find the position # of rightmost set bit. def getFirstSetBitPos(n): return ( int )(math.log(n & - n) / math.log( 2 )) + 1 # Function to find the # previous smaller integer def previousSmallerInteger(n): # position of rightmost set bit of n pos = getFirstSetBitPos(n) # turn off or unset the bit # at position 'pos' return (n & ~( 1 << (pos - 1 ))) # Driver code n = 25 print ( "Previous small Integer = " , previousSmallerInteger(n)) # This code is contributed by Anant Agarwal. |
C#
// C# implementation to find the previous // smaller integer with one less number of // set bits using System; class GFG { // function to find the position of // rightmost set bit. static int getFirstSetBitPos( int n) { return ( int )(Math.Log(n & -n) / Math.Log(2)) + 1; } // function to find the previous smaller // integer static int previousSmallerInteger( int n) { // position of rightmost set bit of n int pos = getFirstSetBitPos(n); // turn off or unset the bit at // position 'pos' return (n & ~(1 << (pos - 1))); } // Driver code public static void Main() { int n = 25; Console.WriteLine( "Previous small Integer =" + previousSmallerInteger(n)); } } // This code is contributed by anant321. |
PHP
<?php // PHP implementation to find the previous // smaller integer with one less number of // set bits // function to find the position of // rightmost set bit. function getFirstSetBitPos( $n ) { return log( $n & - $n ) + 1; } // function to find the previous // smaller integer function previousSmallerInteger( $n ) { // position of rightmost set bit of n $pos = getFirstSetBitPos( $n ); // turn off or unset the bit at // position 'pos' return ( $n & ~(1 << ( $pos - 1))); } // Driver Code $n = 25; echo "Previous smaller Integer = " , previousSmallerInteger( $n ); // This code is contributed by Ajit ?> |
Javascript
<script> // Javascript implementation to find the previous // smaller integer with one less number of // set bits // function to find the position of // rightmost set bit. function getFirstSetBitPos(n) { return parseInt(Math.log(n & -n)/Math.log(2)) + 1; } // function to find the previous smaller // integer function previousSmallerInteger(n) { // position of rightmost set bit of n var pos = getFirstSetBitPos(n); // turn off or unset the bit at // position 'pos' return (n & ~(1 << (pos - 1))); } // Driver program var n = 25; document.write( "Previous smaller Integer = " + previousSmallerInteger(n)); </script> |
Output
24
Time Complexity: O(1)
Auxiliary Space: O(1)