Looking for advice on how to do some bit-twiddling

Question

Suppose I have the array

int a[] = new int[] { 0xBCDA, 0xABFE, 0xBCAD, 0xEFCA, 0xFFCA }

I know that there is always some hexadecimal number which occurs in all number or in this case
A is repeated in the array everywhere so my aim is print only the repeated number and other numbers should be zero,

so my new array should be like this

0x000A, 0xA000, 0x00A0, 0x000A, 0x000A

Any idea?

p.s this is not homework

Answer 1

You didn't say what language, so I will coach this in terms of C. Fill in indices and loops as needed, but the body would be four lines, one for each digit. && is logical and. || (|=) is logical or.

if ((a[ ] && 0x000F) == 0x000A) r[ ] |= 0x000A;

if ((a[ ] && 0x00F0) == 0x00A0) r[ ] |= 0x00A0;

etc...

Answer 2

Well you are using Java, and you say that this is a set-intersection problem. So let's model the problem in a nice OO way.

public final class HexDigit
{
    public static HexDigit[] parseDigits(int v)
    {
        HexDigit[] rval = new HexDigit[8];
        int mask = 15;
        for(int i = 0; i < 16; i++)
        {
            rval[i] = new HexDigit((byte) v&mask);
            v = v >> 4;
        }
        return rval;
    }
    final static char[] hDigits = 
    {
        '0' ,'1','2' ,'3','4' ,'5' ,
        '6','7','8','9','a','b',
        'c','d','e','f','g','h',
        'i','j','k','l','m','n',
        'o','p','q','r','s','t' ,
        'u','v','w','x','y','z'
    };

    public HexDigit(byte v)
    {
        assert(v >=0 && v < 16, "values is outside of the appropriate range for an Hexadecimal Digit");
        digit = v;
    }
    private byte digit;
    public String toString()
    {
        return hDigits[digit];
    }
    public byte getValue()
    {
        return digit;
    }
    public int hashCode()
    {
        return digit;
    }
    public bool equals(Object o)
    {
        return (o instanceof HexDigit && ((HexDigit)o).digit == this.digit);
    }
}

Now that we have a nice way to model our digits (and more imporantly it will play nice with a hashset) let's solve our problem:

int a[] = your input array;
Set<HexDigit> intersection =null;
for(int i = 0; i < a.length; i++)
{
    HexDigits[] digits = HexDigit.parseDigits(a[i]);
    Set<HexDigit> digits = new HashSet<HexDigit>(digits);
    if(intersection == null)//we are the first one
    {
        intersection = digits;
    }
    else
    {
        intersection.retainAll(digits);
    }
}
//done!

At the end intersection will contain only those digits that were in each word.

Answer 3

There's a really simple way to do this. Since you know that each element of a[] is effectively a set of four hexadecimal digits, you can create a bitset for each element of a[]. The bitwise AND for all those masks will tell you which hexidecimal digit exists in all of them. Then, you simply do a second pass over a[] and write out the hexadecimal digit if it exists in the mask or 0 if it doesn't for each hexadecimal digit.