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.
1
of 1 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;
}

- oOZz June 20, 2013 | Flag Reply
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;

- rotinom June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- oOZz June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- rotinom June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- oOZz June 20, 2013 | Flag
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 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;
}

- Mustafa Bedel July 18, 2013 | Flag Reply
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);
}

- vathsala September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- aka June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You take the int part

- Anonymous June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- aka June 21, 2013 | Flag
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).

- gayathri.jeyaram.k June 20, 2013 | Flag Reply
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)

- Anonymous June 20, 2013 | Flag Reply
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

- Amit June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simulation of PAVGB in SIMD.
sites.google.com/site/spaceofjameschen/home/number-and-string/simd-simulation

- Anonymous June 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a second solution is using masks
sites.google.com/site/spaceofjameschen/home/number-and-string/simd-simulation---method2----ittiam

- Anonymous June 21, 2013 | Flag Reply
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;

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))));
	}
}

- Murali Mohan June 21, 2013 | Flag Reply
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;


}

- Bhuvan February 07, 2014 | Flag Reply
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);
}

- Rohan G Thomas May 14, 2014 | Flag Reply
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'

- whatevva' June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amit June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- whatevva' June 20, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More