Given an integer N, the task is to find an integer M formed by taking the rightmost set bit in N i.e. the only set bit in M will be the rightmost set bit in N and the rest of the bits will be unset.
Examples:
Input: N = 7
Output: 1
7 = 111, the number formed by the last set bit is 001 i.e. 1.
Input: N = 10
Output: 2
10 = 1010 -> 0010 = 2
Input: N = 16
Output: 16
Approach:
- Store x = n & (n – 1) which will unset the first set bit from the right in n.
- Now, update n = n ^ x to set the changed bit and unset all the others which is the required integer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the integer formed// by taking the rightmost set bit in nint firstSetBit(int n){ // n & (n - 1) unsets the first set // bit from the right in n int x = n & (n - 1); // Take xor with the original number // The position of the 'changed bit' // will be set and rest will be unset return (n ^ x);}// Driver codeint main(){ int n = 12; cout << firstSetBit(n); return 0;} |
Java
// Java implementation of the approachclass neveropen{ // Function to return the integer formed // by taking the rightmost set bit in n public static int firstSetBit(int n) { // n & (n - 1) unsets the first set // bit from the right in n int x = n & (n-1); // Take xor with the original number // The position of the 'changed bit' // will be set and rest will be unset return (n ^ x); } // Driver Code public static void main (String[] args) { int n = 12; System.out.println(firstSetBit(n)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach# Function to return the integer formed# by taking the rightmost set bit in ndef firstSetBit(n): # n & (n - 1) unsets the first set # bit from the right in n x = n & (n - 1) # Take xor with the original number # The position of the 'changed bit' # will be set and rest will be unset return (n ^ x)# Driver coden = 12print(firstSetBit(n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;class neveropen{ // Function to return the integer formed // by taking the rightmost set bit in n public static int firstSetBit(int n) { // n & (n - 1) unsets the first set // bit from the right in n int x = n & (n-1); // Take xor with the original number // The position of the 'changed bit' // will be set and rest will be unset return (n ^ x); } // Driver Code public static void Main () { int n = 12; Console.WriteLine(firstSetBit(n)); }}// This code is contributed by// anuj_67.. |
Javascript
<script>// JavaScript implementation of the approach// Function to return the integer formed// by taking the rightmost set bit in nfunction firstSetBit(n){ // n & (n - 1) unsets the first set // bit from the right in n let x = n & (n - 1); // Take xor with the original number // The position of the 'changed bit' // will be set and rest will be unset return (n ^ x);}// Driver code let n = 12; document.write(firstSetBit(n));// This code is contributed by Manoj.</script> |
Output:
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
