## Ittiam Systems Interview Question for Systems Design Engineers

Team: Bangalore EE team
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Unless there is another bitwise trick, you can use a union:

``````union 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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;``````

Comment hidden because of low score. Click to expand.
0

@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"

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

@rotinom Well, that's still masking, because you're shifting with zero fill :)) Otherwise, you would write (A << 24) >> 25 as A >> 1.

However, you have a good point, because the question is not clear about that.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````// 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 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;

}

printf("result is %X\n", result);

char ch = _getch();

return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <stdio.h>

int a = 0x04030201;
int b = 0x08070605;
int c = 0;

void main()
{

char *a1 = (char *)&a;
char *b1 = (char *)&b;
char *c1 = (char *)&c;
int i = 0;
for(i=0;i<4;i++) *(c1+i) = (*(a1+i) + *(b1+i))/2;
printf("%x\n",c);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

How will you represent (14+5)/2 in 4 bits?

Comment hidden because of low score. Click to expand.
0

You take the int part

Comment hidden because of low score. Click to expand.
0

What is wrong with binary addition and doing right shift by one?

Comment hidden because of low score. Click to expand.
0

ok, so here is the code.

``````int main()
{
int x = 4454412;
int y = 56;
char *x_8 = (char *)&x;
char *y_8 = (char *)&y;
printf("%d\n", (*x_8+*y_8)>>1);
printf("%d %d\n", *x_8, *y_8);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is a byte, not 4 bits, it is 8bits.
A3, A2, A1 and A0 are single bytes that make up A. The same holds good for B and C.

A, B and C are integers (32 bits) or (4bytes).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

do the following
1.let x=A & (01010101)x
means 01010101 in hex and y=B &(01010101)x
2.let z=x&y
3.A>>=1,B>>=1
4.A&=(7F7F7F7F)x and B&==(7F7F7F7F)x
5.C=A+B+z

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simulation of PAVGB in SIMD.

Comment hidden because of low score. Click to expand.
0
of 0 vote

a second solution is using masks

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

static int fa, fb;

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;

count++;
}

maskComplement = 1 << count - 1;
if ((mask & i) != 0) {
}
}
return rev;
}

public static String zeroPrefixHexString(String s) {
return "0x0000000".substring(0, 10 - s.length()) + s;
}

public static void main(String[] args) {
System.out.println("C="
+ zeroPrefixHexString(Integer.toHexString(computeSum(fa, fb))));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
void main(){
int a = 0x09090909, b= 0x01010101,c=0;
unsigned char *p,*q,*r;
p=(unsigned char *)&a;
q=(unsigned char *)&b;
r=(unsigned char *)&c;
*(r)=(*(p)+*(q))>>1;
*(r+1)=(*(p+1)+*(q+1))>>1;
*(r+2)=(*(p+2)+*(q+2))>>1;
*(r+3)=(*(p+3)+*(q+3))>>1;
printf("%x",c);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

A = A3A2A1A0
B = B3B2B1B0

A' = (A & 0xf7f7f7f7) >> 2
B' = (B & 0xf7f7f7f7) >> 2

C = A' + B'

Comment hidden because of low score. Click to expand.
0

For A=15,B=13,you will get C=13,but C must be 14

Comment hidden because of low score. Click to expand.
0

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
A_p = (A & 0xfEfEfEfE) >> 1
B_p = (B & 0xfEfEfEfE) >> 1
C_p = A_p + B_p

## reclaim the carry information for the Lsb
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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.