/****************************************************************************
* Author: Isai Damier
* Title: Find Odd Singleton
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Given an array of floating point numbers where all values occur an even
* number of times; except for one value, which occurs an odd number of
* times and which we shall call a singleton; find the singleton.
*
* Sample Input: float fArr[] = {1.2f, 7.340f, 2.3f, 3.34f, 7.340f, 4.567f,
* 5.65f, 6.234f, 7.340f, 4.567f, 7.340f, 2.3f,
* 6.234f, 7.340f, 3.34f, 1.2f, 5.65f};
* Sample Output: 7.340f
*
* Technical Details:
* The most efficient approach is to XOR all the elements of the array and
* return the result. Recall from digital logic the following truths about
* the XOR (^) operator: x^x = 0; 0^x = x.
* (Ref http://www.teahlab.com/basicGates/xorgate).
*
* However, there is still one problem: Java does not define bitwise
* operations for float. Therefore, the following steps are followed to
* find the singleton:
* 0] Convert each floating point number to Java's virtual
* intBits using Float.floatToIntBits(float f).
* 1] Perform XOR operation on the values while in intBits form.
* 2] Convert the final intBits result to float using Java's
* Float.intBitsToFloat(int i).
* 3] Return the final float value.
*
* Note: Java's intBits (which does not exist in fact) are based
* on the IEEE 754 floating-point single-precision format.
*
***************************************************************************/
public float findOddSingleton(float[] a) {
int b = Float.floatToIntBits(a[0]);
for (int n = 1; n < a.length; n++) {
b ^= Float.floatToIntBits(a[n]);
}
return Float.intBitsToFloat(b);
}
import org.junit.Test;
import static org.junit.Assert.*;
public class BitwiseTest {
/**
* Test of findOddSingleton method, of class Bitwise.
*/
@Test
public void testFindOddSingleton_float() {
System.out.println(""findOddSingleton"");
float fArr[] = {1.2f, 7.340f, 2.3f, 3.34f, 7.340f, 4.567f, 5.65f,
6.234f, 7.340f, 4.567f, 7.340f, 2.3f,
6.234f, 7.340f, 3.34f, 1.2f, 5.65f};
Bitwise bits = new Bitwise();
float expResult = 0.0F;
assertTrue(7.340f == bits.findOddSingleton(fArr));
}
}
