Given two non-negative integers a and b. The problem is to find the position of the rightmost bit where a carry is generated in the binary addition of a and b.
Examples:
Input : a = 10, b = 2 Output : 2 (10)10 = (1010)2 (2)10 = (10)2. 1010 + 10 As highlighted, 1st carry bit from the right will be generated at position '2'. Input : a = 10, b = 5 Output : 0 '0' as no carry bit will be generated.
Approach: Following are the steps:
- Calculate num = a & b.
- Find the position of rightmost set bit in num.
C++
// C++ implementation to find the position of// rightmost bit where a carry is generated first#include <bits/stdc++.h>using namespace std;typedef unsigned long long int ull;// function to find the position of// rightmost set bit in 'n'unsigned int posOfRightmostSetBit(ull n){ return log2(n & -n) + 1;}// function to find the position of rightmost// bit where a carry is generated firstunsigned int posOfCarryBit(ull a, ull b){ return posOfRightmostSetBit(a & b);}// Driver program to test aboveint main(){ ull a = 10, b = 2; cout << posOfCarryBit(a, b); return 0;} |
Java
// Java implementation to find the position of// rightmost bit where a carry is generated firstclass GFG { // function to find the position of // rightmost set bit in 'n' static int posOfRightmostSetBit(int n) { return (int)(Math.log(n & -n) / Math.log(2)) + 1; } // function to find the position of rightmost // bit where a carry is generated first static int posOfCarryBit(int a, int b) { return posOfRightmostSetBit(a & b); } // Driver code public static void main(String[] args) { int a = 10, b = 2; System.out.print(posOfCarryBit(a, b)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 implementation to find the position of# rightmost bit where a carry is generated firstimport math# function to find the position of# rightmost set bit in 'n'def posOfRightmostSetBit( n ): return int(math.log2(n & -n) + 1) # function to find the position of rightmost# bit where a carry is generated firstdef posOfCarryBit( a , b ): return posOfRightmostSetBit(a & b)# Driver program to test abovea = 10b = 2print(posOfCarryBit(a, b))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# implementation to find the position of// rightmost bit where a carry is generated firstusing System;class GFG { // function to find the position of // rightmost set bit in 'n' static int posOfRightmostSetBit(int n) { return (int)(Math.Log(n & -n) / Math.Log(2)) + 1; } // function to find the position of rightmost // bit where a carry is generated first static int posOfCarryBit(int a, int b) { return posOfRightmostSetBit(a & b); } // Driver code public static void Main() { int a = 10, b = 2; Console.Write(posOfCarryBit(a, b)); }}// This code is contributed by Sam007. |
Javascript
<script>// Javascript implementation to find the // position of rightmost bit where a carry// is generated first // Function to find the position of // rightmost set bit in 'n' function posOfRightmostSetBit(n) { return parseInt(Math.log(n & -n) / Math.log(2)) + 1; } // Function to find the position of rightmost // bit where a carry is generated first function posOfCarryBit(a, b) { return posOfRightmostSetBit(a & b); } // Driver codevar a = 10, b = 2; document.write(posOfCarryBit(a, b)); // This code is contributed by noob2000</script> |
Output:
2
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!
