Ittiam Systems Interview Question Systems Design Engineers
Team: Bangalore EE team
Country: India
Interview Type: In-Person
My "bitwise" trick is inefficient, but if you bitshift left, then bitshift right+1 bit for each byte in A & B, then add them, then shift back to final location. Repeat for all bytes.
Pseudo-code:
int C =
(A << 24) >> 25 + (B << 24) >> 25 |
((A << 16) >> 25 + (B << 16) >> 25) << 8 |
((A << 8) >> 25 + (B << 8) >> 25) << 16 |
((A >> 25) + (B >> 25)) << 24;
@Up The question says "Without using the obvious method of masking out each byte of A and corresponding byte of B, and add them, and then right-shifting once"
Right, but it's not bitmasking. It's using bit manipulations. Bitmasking would be like:
C1 = (A & 0x000000FF + B & 0x000000FF) >> 1
where the 0x000000FF is the mask to manipulate the individual bits. My technique doesn't do the "obvious" (traditional) method of it. It takes advantage of the fact that when you bitshift a value, it pads the values with 0's. This is performing the same task (allowing you to only work on the bits you care about)
// bit_calculate.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
// Modify C such that
// C0=(A0+B0)/2
// C1=(A1+B1)/2
// C2=(A2+B2)/2
// C3=(A3+B3)/2
// C = 22334455
int _tmain(int argc, _TCHAR* argv[])
{
int A = 0x00112233;
int B = 0x44556677;
int C = 0x8899AABB;
int amask = 0xFF;
int bmask = 0xFF;
int abyte = 0;
int bbyte = 0;
int result = 0;
for (int i = 0; i < 4; i++)
{
abyte = A & amask; // 00112233 & 000000FF --> 00000033
bbyte = B & bmask; // 44556677 & 000000FF --> 00000077
result |= (abyte + bbyte) / 2;
amask <<= 8;
bmask <<= 8;
}
printf("result is %X\n", result);
char ch = _getch();
return 0;
}
Slow as hell, but this works using only divisions (in place of right shifts), modulos (instead of masks) and multiplication (as left shifts).
def bin_format(x, digits=32):
s = str(bin(x))[2:].zfill(digits)
return s[:8] + " " + s[8:16] + " " + s[16:24] + " " + s[24:]
def test_solution(a, b, c):
assert (a % 256 + b % 256) % 256 / 2 == c % 256
for _ in xrange(3):
a = a >> 8
b = b >> 8
c = c >> 8
assert (a % 256 + b % 256) % 256 / 2 == c % 256
from random import randrange
MAX_INT = 2 ** 30
def test(n):
for _ in xrange(n):
a = randrange(MAX_INT)
b = randrange(MAX_INT)
try:
test_solution(a, b, byte_by_byte_avg(a, b))
except AssertionError as e:
print "\n".join([bin_format(a), bin_format(b), bin_format(byte_by_byte_avg(a, b))])
raise e
def byte_by_byte_avg(a, b):
#assuming a and b are positive
return ((a + b) % 256 / 2 +
(((a / 256 + b / 256) % 256) / 2) * 256 +
(((a / 65536 + b / 65536) % 256) / 2) * 65536 +
(((a / 16777216 + b / 16777216) % 256) / 2) * 16777216)
if __name__ == '__main__':
test(100)
If we think in terms of the reverse of a word, the operation of adding the bytes and dividing them by 2 seems to get simplified. The notion of adding the bytes and shifting them to one position right in a regular word, transforms, in a reversed word, to ignoring the result of addition of LSBs in each byte of the input words.
Based on the above notion, the following principle worked.
1. Run an index, i from 1 to 32
2. Extract the ith bit from the words of A and B. (This can done by extracting their LSBs and then shifting them one position to the right.)
3. Add the ith bits of both A and B and store the values of result and carry.
4 if (i % 8 == 1) shift C one position to the left and add the carry
5 if (i % 8 != 1) compute the result of adding ith bits of A and B, shift C one position to the left and add the result.
6. In the end, reverse C and print the value.
Tested the following program with inputs:
0x7FFFFFFF (maximum integral value in Java)
0x7FFFFFFF (outputs 0x7FFFFFFF)
0x00000100
0x00000300 (outputs 0x00000200)
0x7aacacac
0x7ccecece (outputs 0x7bbdbdbd)
import java.util.Scanner;
import java.util.regex.Pattern;
public class BytewiseAddition {
static int fa, fb;
public static void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System
.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(delimiters);
System.out.println("First number:");
if (scanner.hasNext()) {
String ip = scanner.next();
if (ip.toLowerCase().startsWith("0x")) {
ip = ip.substring(2);
}
fa = Integer.parseInt(ip, 16);
}
System.out.println("Second number:");
if (scanner.hasNext()) {
String ip = scanner.next();
if (ip.toLowerCase().startsWith("0x")) {
ip = ip.substring(2);
}
fb = Integer.parseInt(ip, 16);
}
}
public static int computeSum(int a, int b) {
int i = 1, c = 0, previousCarry = 0, nextCarry = 0, tmp = 0;
while (i <= 32) {
if (i % 8 == 1) {
c = (c << 1) | previousCarry;
previousCarry = 0;
}
tmp = (a & 1) + (b & 1) + previousCarry;
nextCarry = (tmp & 2) >>> 1;
tmp &= 1;
a = a >>> 1;
b = b >>> 1;
if (i % 8 != 1) {
c = (c << 1) | tmp;
}
i++;
previousCarry = nextCarry;
}
c = (c << 1) | previousCarry;
return revBitString(c);
}
public static int revBitString(int i) {
int mask = 1, rev = 0, maskComplement = 1, count = 0;
while (maskComplement != 0) {
maskComplement = maskComplement << 1;
count++;
}
maskComplement = 1 << count - 1;
while (mask != 0) {
if ((mask & i) != 0) {
rev = rev | maskComplement;
}
maskComplement = maskComplement >>> 1;
mask = mask << 1;
}
return rev;
}
public static String zeroPrefixHexString(String s) {
return "0x0000000".substring(0, 10 - s.length()) + s;
}
public static void main(String[] args) {
readInput();
System.out.println("C="
+ zeroPrefixHexString(Integer.toHexString(computeSum(fa, fb))));
}
}
void sum_octet(int num1, int num2, int num3)
{
char *pt1 = reinterpret_cast<char *> (&num1);
char *pt2 = reinterpret_cast<char *> (&num2);
char *pt3 = reinterpret_cast<char *> (&num3);
cout << std::hex << num1 << endl;
cout << std::hex << num2 << endl;
cout << std::hex << num3 << endl;
cout << "Sum1 : " << (*pt1) + (*pt2) + (*pt3) << endl;
cout << "Sum2 : " << (*++pt1) + (*++pt2) + (*++pt3) << endl;
cout << "Sum3 : " << (*++pt1) + (*++pt2) + (*++pt3) << endl;
cout << "Sum4 : " << (*++pt1) + (*++pt2) + (*++pt3) << endl;
}
A = A3A2A1A0
B = B3B2B1B0
A' = (A & 0xf7f7f7f7) >> 2
B' = (B & 0xf7f7f7f7) >> 2
C = A' + B'
acknowledge the error in the code above .. following is the updated algo. The actul code is in the subroutine "actual"
def reference(A, B):
C0 = ((A & 0xff) + (B & 0xff))>>1
C1 = (((A>>8) & 0xff) + ((B>>8) & 0xff))>>1
C2 = (((A>>16) & 0xff) + ((B>>16) & 0xff))>>1
C3 = (((A>>24) & 0xff) + ((B>>24) & 0xff))>>1
C = C0 + (C1<<8) + (C2<<16) + (C3<<24)
return C
def actual(A,B):
## apply mask so that there is no carry that
## carries over from one byte to another byte
## .. we will lose information on the carry for
## for the lsb additions
A_p = (A & 0xfEfEfEfE) >> 1
B_p = (B & 0xfEfEfEfE) >> 1
C_p = A_p + B_p
## reclaim the carry information for the Lsb
## additions
A_pp = A & 0x01010101
B_pp = B & 0x01010101
C_pp = ((A_pp + B_pp)>>1) & 0x01010101
C = C_p + C_pp
return C
## MAIN
A=0x335577FF
B=0xFFDDBB99
print 'reference: %x' % reference(A,B)
print 'actual : %x' % actual(A,B)
Unless there is another bitwise trick, you can use a union:
- oOZz June 20, 2013union uintbyte { unsigned int val; char[4] bytes; } unsigned int computeByteSum(unsigned int A, unsigned int B) uintbyte bA; uintbyte bB; uintbyte bC; bA.val = A; bB.val = B bC.bytes[0] = (bA.bytes[0] + bB.bytes[0]) >> 1; bC.bytes[1] = (bA.bytes[1] + bB.bytes[1]) >> 1; bC.bytes[2] = (bA.bytes[2] + bB.bytes[2]) >> 1; bC.bytes[3] = (bA.bytes[3] + bB.bytes[3]) >> 1; return bC.val; }