Given two decimal numbers num1 and num2, the task is to count the number of times carry operation is required while adding the two given numbers in binary form.
Examples:
Input: num1 = 15, num2 = 10
Output: 3
Explanation:
Give numbers are added as:
15 -> 1 1 1 1
10 -> 1 0 1 0
carry -> 1 1 1 – –
——————————
25 -> 1 1 0 0 1Input: num1 = 14 num2 = 4
Output: 2
Explanation:
Give numbers are added as:
14 -> 1 1 1 0
4 -> 0 1 0 0
carry -> 1 1 – – –
——————————
18 -> 1 0 0 1 0
Naive Approach: The naive idea is to convert the numbers into binary and add a bit one by one starting from Least Significant Bit and check if carry is generated or not. Whenever a carry is generated then increase the count by 1. Print count of carry after all the steps.
Time Complexity: O(K), where K is a count of the number of digits in the binary representation of X.
Auxiliary Space: O(log N)
Efficient Approach: The idea is to use Bitwise XOR and AND. Below are the steps:
- Add the two binary numbers using XOR and AND.
- Now, the number of 1’s in the Bitwise AND of two numbers shows the number of carry bits at that step.
- Add the number of one’s in each stage in the above step to get the final count of carry operation.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of carry// operations to add two binary numbersint carryCount(int num1, int num2){ // To Store the carry count int count = 0; // Iterate till there is no carry while (num2 != 0) { // Carry now contains common // set bits of x and y int carry = num1 & num2; // Sum of bits of x and y where at // least one of the bits is not set num1 = num1 ^ num2; // Carry is shifted by one // so that adding it to x // gives the required sum num2 = carry << 1; // Adding number of 1's of // carry to final count count += __builtin_popcount(num2); } // Return the final count return count;}// Driver Codeint main(){ // Given two numbers int A = 15, B = 10; // Function Call cout << carryCount(15, 10); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count the number of carry// operations to add two binary numbersstatic int carryCount(int num1, int num2){ // To Store the carry count int count = 0; // Iterate till there is no carry while (num2 != 0) { // Carry now contains common // set bits of x and y int carry = num1 & num2; // Sum of bits of x and y where at // least one of the bits is not set num1 = num1 ^ num2; // Carry is shifted by one // so that adding it to x // gives the required sum num2 = carry << 1; // Adding number of 1's of // carry to final count count += Integer.bitCount(num2); } // Return the final count return count;}// Driver Codepublic static void main(String[] args){ // Given two numbers int A = 15, B = 10; // Function call System.out.print(carryCount(A, B));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function to count the number of carry # operations to add two binary numbersdef carryCount(num1, num2): # To Store the carry count count = 0 # Iterate till there is no carry while(num2 != 0): # Carry now contains common # set bits of x and y carry = num1 & num2 # Sum of bits of x and y where at # least one of the bits is not set num1 = num1 ^ num2 # Carry is shifted by one # so that adding it to x # gives the required sum num2 = carry << 1 # Adding number of 1's of # carry to final count count += bin(num2).count('1') # Return the final count return count# Driver Code# Given two numbersA = 15B = 10# Function callprint(carryCount(A, B))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{ static int countSetBits(int x){ int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;}// Function to count the number of carry// operations to add two binary numbersstatic int carryCount(int num1, int num2){ // To Store the carry count int count = 0; // Iterate till there is no carry while (num2 != 0) { // Carry now contains common // set bits of x and y int carry = num1 & num2; // Sum of bits of x and y where at // least one of the bits is not set num1 = num1 ^ num2; // Carry is shifted by one // so that adding it to x // gives the required sum num2 = carry << 1; // Adding number of 1's of // carry to readonly count count += countSetBits(num2); } // Return the readonly count return count;}// Driver Codepublic static void Main(String[] args){ // Given two numbers int A = 15, B = 10; // Function call Console.Write(carryCount(A, B));}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// JavaScript program for the// above approach function countSetBits(x){ let setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;}// Function to count the number of carry// operations to add two binary numbersfunction carryCount(num1, num2){ // To Store the carry count let count = 0; // Iterate till there is no carry while (num2 != 0) { // Carry now contains common // set bits of x and y let carry = num1 & num2; // Sum of bits of x and y where at // least one of the bits is not set num1 = num1 ^ num2; // Carry is shifted by one // so that adding it to x // gives the required sum num2 = carry << 1; // Adding number of 1's of // carry to readonly count count += countSetBits(num2); } // Return the readonly count return count;}// Driver Code // Given two numbers let A = 15, B = 10; // Function call document.write(carryCount(A, B));</script> |
3
Time Complexity: O(log2(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] There you will find 10265 more Information on that Topic: geeksforgeeks.org/count-of-carry-operations-on-adding-two-binary-numbers/ […]
… [Trackback]
[…] There you will find 13261 more Info on that Topic: geeksforgeeks.org/count-of-carry-operations-on-adding-two-binary-numbers/ […]