67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

Approach : The idea is to start from the right and keep adding digits and forwarding carry (if any). Also, take care of the case when one of them gets exhausted. For that, keep adding zero to the other one and forward carry if required. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

string Solution::addBinary(string a, string b) { int lenA = a.length(), lenB = b.length(); int i = lenA - 1, j = lenB - 1; int carry = 0; stack<char> out; int sum = 0; while(i >= 0 || j >= 0){ if(i >= 0 && j >= 0){ //convert to int and add sum = a[i] - '0' + b[j] - '0' + carry; i--; j--; } else{ //string a is exhausted if(i < 0){ sum = b[j] - '0' + carry; j--; } //string b is exhausted else{ sum = a[i] - '0' + carry; i--; } } //setting the carry accordingly if(sum > 1){ carry = 1; }else{ carry = 0; } sum = sum % 2; //convert back to character char aChar = '0' + sum; out.push(aChar); } //for final carry if(carry){ out.push('1'); } string res = ""; //reverse the output while(!out.empty()){ res = res + out.top(); out.pop(); } return res; }

Here is the link to the ideone solution : http://ideone.com/o5r3Eq

Read More

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of 1 bits it contains.

Example:

The 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the output should be 3.

Approach: The efficient method is to use an unsigned number and keep left shifting it 32 times and keeping the ones count if a one is found at the current bit position.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<iostream> using namespace std; int num1Bits(unsigned int a){ if(a <= 0){ return 0; } int count = 0; while(a != 0){ if(a%2 == 1){ count++; } a = a >> 1; } return count; } int num1BitsEfficient(unsigned int A){ int count = 0; unsigned int bit = 1; for(int i = 0; i <= 32; i++){ if(bit & A){ count++; } bit = bit << 1; } return count; } int main(){ unsigned int a = 11; cout << num1Bits(a) << endl; cout << num1BitsEfficient(a) << endl; return 0; }

Read More