Google Interview Question Software Engineer in Tests
Country: United States
Yeah this was a great tutorial to understand this conversion.
I wrote a small program to convert the binary code into Gray code using iteration based on this tutorial if someone would be interested.
#include <iostream>
template <typename T>
void set_bit(T& value, size_t n)
{
value = value | (1 << n);
}
template <typename T>
bool is_bit_set(T value, size_t n)
{
return 0 == (value & (1 << n)) ? false : true;
}
template <typename T>
T binary_to_gray_iterative(T binary, size_t number_of_bits = 8 * sizeof(T))
{
T gray = T();
for (size_t i = 0; i < number_of_bits - 1; ++i) {
if (is_bit_set(binary, i) != is_bit_set(binary, i + 1)) {
set_bit(gray, i);
}
}
if (is_bit_set(binary, number_of_bits - 1)) {
set_bit(gray, number_of_bits - 1);
}
return gray;
}
template <typename T>
void print_binary_code(T element)
{
for (int i = 8 * sizeof(T) - 1; i >= 0; --i) {
std::cout << (0 == (element & (1 << i)) ? 0 : 1);
}
std::cout << std::endl;
}
int main (int argc, const char * argv[])
{
char binary = 0x7B;
print_binary_code(binary);
char gray = binary_to_gray_iterative(binary);
print_binary_code(gray);
return 0;
}
gray code is given by XOR the current bit (position i) with previous bit of the binary code (position i+1). To reverse the conversion one has to make sure to compute the binary bit at position i+1 first, to know the filter for position i.
Algorithm is here given with array of digits [1,0,1,1,0] for clarity. It can easily be translated into operations on bits of an unsigned number as shown below the ==== line.
def binary2gray( code, invert_bit = 0 ):
if len(code)==0:
return []
bit = code[0]
return [ bit ^ invert_bit ] + binary2gray( code[1:], bit )
def gray2binary( code, invert_bit = 0 ):
if len(code)==0:
return []
bit = code[0]
return [ bit ^ invert_bit ] + gray2binary( code[1:], bit ^ invert_bit )
==============================================
assuming 32-bit numbers
def xbinary2gray( x, pos = 31, invert_bit = 0 ):
if pos < 0:
return x
mask = 1<<pos
newx = (mask & ( x ^ invert_bit )) | (~mask & x)
return xbinary2gray( newx, pos - 1, (mask&x) >> 1 )
def xgray2binary( x, pos = 31, invert_bit = 0 ):
if pos < 0:
return x
mask = 1<<pos
newx = (mask & ( x ^ invert_bit )) | (~mask & x)
return xgray2binary( newx, pos - 1, (mask&newx) >> 1 )
Here is C++ solution...!!!
#include<iostream>
#include<vector>
using namespace std;
void G2B(const vector<int>& Gvec, vector<int>& result){
int bSize = Gvec.size();
int gSize = result.size();
if (bSize == gSize)
return;
if (!gSize)
result.push_back(Gvec[0]);
else
{
int temp = Gvec[gSize] ^ result[gSize - 1];
result.push_back(temp);
}
G2B(Gvec, result);
}
void B2G(const vector<int>& Bvec, vector<int>& result){
int bSize = Bvec.size();
int gSize = result.size();
if (bSize == gSize)
return;
if (!gSize)
result.push_back(Bvec[0]);
else
{
int temp = Bvec[gSize] ^ Bvec[gSize - 1];
result.push_back(temp);
}
B2G(Bvec, result);
}
int main(){
vector<int> vec = { 1, 0, 1, 1 ,0 ,1 ,0 ,1 ,1 }; //Input
vector<int> Gresult, Bresult; //Output
B2G(vec, Gresult); //Binary to Gray
G2B(Gresult, Bresult); //Gray to Binary
for (int i = 0; i < Bresult.size(); i++)
cout << Bresult[i] << " ";
cout << endl;
return 0;
}
void DisplayGray(string str, int nBits);
void DisplayGrayReverse(string str, int nBits);
void DisplayGrayReverse(string str, int nBits) {
if(nBits == 0)
cout << str << endl;
else {
string newStr1 = str + '1';
DisplayGray(newStr1, nBits - 1);
string newStr2 = str + '0';
DisplayGrayReverse(newStr2, nBits - 1);
}
}
void DisplayGray(string str, int nBits) {
if(nBits == 0)
cout << str << endl;
else {
string newStr1 = str + '0';
DisplayGray(newStr1, nBits - 1);
string newStr2 = str + '1';
DisplayGrayReverse(newStr2, nBits - 1);
}
}
void GenerateGrayCodes(int nBits) {
DisplayGray("", nBits);
}
int main() {
cout << "Enter no of bits: ";
int nBits;
cin >> nBits;
GenerateGrayCodes(nBits);
return 0;
}
Gray code can be obtained from binary code by flipping bits recursively
algo outline
function B2G :
we keep MSB;
flip the rest bits
and call B2G(flipped rest bits);
e.g. decimal 10 = 1010 in binary
B2G(1010)
= 1 + B2G(flip(010))
= 1 + B2G(101)
= 11 + B2G(flip(01))
= 11 + B2G(10)
= 111 + B2G(flip(0))
= 111 + B2G(1)
= 1111
incidently B2G is also G2B
once you know how many bits then the conversion is easy:
unsigned int ConvertGray (unsigned int number, int number_of_bits) {
if (number_of_bits == 0) {
return (number);
}
else {
number = (((1 << (number_of_bits - 1)) & number) | ~((pow(2,number_of_bits) - 1) & number))
return (ConvertGray (number, (number_of_bits - 1));
}
}
void B2G(char binary[], char gray[])
{
char prev = '0';
while(!*binary){
if(prev == '0')
*gray = *binary;
else
*gray = *binary == '0'?'1':'0';
prev = *binary;
gray++;
binary++;
}
}
void G2B(char gray[], char binary[])
{
char prev = '0';
while(!*gray){
if(prev == '0')
*binary = *gray;
else
*binary = *gray == '0'?'1':'0';
prev = *binary;
gray++;
binary++;
}
}
can refactor previous two to one function
void convert(char src[], char dest[], bool B2G)
{
char prev = '0';
while(!*src){
if(prev == '0')
*dest = *src;
else
*dest = *src == '0'?'1':'0';
prev = B2G?*src:*dest;
src++;
dest++;
}
}
public static int b2g(int b){
return b2g(b, length(b)-1);
}
// invoke b2g(5, 2)
public static int b2g(int b, int len) {
if (len == 0)
return b;
return b2g(flipfrom(b, len), len - 1);
}
public static int flipfrom(int b, int start) {
for (int i = start; i > 0; i--) {
b = flipNthBit(b, i);
}
return b;
}
public static int length(int b) {
int c = 0;
while (b != 0) {
c++;
b = b >> 1;
}
return c;
}
public static int flipNthBit(int b, int n) {
return b ^ (1 << (n-1));
}
--- www[dot]wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307
- kanap008 February 29, 2012