Skip to content

Instantly share code, notes, and snippets.

# leondeklerk/Solution.java Last active May 17, 2019

 class Solution { /** * Calculates the hamming code of the given bit sequence. * * @param bitSequence The input bit sequence * @param inputLength The length of the input bit sequence (including possible leading zeros) * @param isEvenParity Boolean indicating if the hamming algorithm should use even parity or not * @return The Hamming code sequence */ static long calcHamming(long bitSequence, int inputLength, boolean isEvenParity) { int redundant = 0; while (!(Math.pow(2, redundant) >=inputLength + redundant + 1)){ redundant++; } int resultLength = inputLength + redundant; bitSequence = bitSequence << redundant; for(int i = redundant; i > 0; i--){ int redPos = (int) Math.pow(2, redundant - i); bitSequence = insertAt(bitSequence, redPos, resultLength); } for(int i = 0; i < redundant; i++){ long pos = (long) Math.pow(2, i); int count = countBits(bitSequence, pos, resultLength); if(count % 2 == 0){ if(isEvenParity) { bitSequence ^= (1L << (resultLength - pos)); } } else { if(!isEvenParity) { bitSequence ^= (1L << (resultLength - pos)); } } } return bitSequence; } /** * Returns the corrected (if needed) hamming code of the given bit sequence. * * @param bitSequence The Hamming code bit sequence * @param inputLength The length of the input bit sequence (including possible leading zeros) * @param isEvenParity Boolean indicating if the hamming algorithm should use even parity or not * @return The correct Hamming code sequence */ static long checkHamming(long bitSequence, int inputLength, boolean isEvenParity) { int redundant = 0; while (!(Math.pow(2, redundant) >= inputLength + 1)){ redundant++; } long bitLoc = 0; for(int i = redundant - 1; i >= 0; i--){ long pos = (long) Math.pow(2, i); int count = countBits(bitSequence, pos, inputLength) + 1; bitLoc <<= 1; if(count % 2 == 0){ if(!isEvenParity) { bitLoc |= 1L; } } else { if (isEvenParity) { bitLoc |= 1L; } } } if(bitLoc == 0){ return bitSequence; } return bitSequence ^ (1L << inputLength - bitLoc); } private static long insertAt(long seq, int pos, int length){ long mask1 = 0; for(int i = 0; i < length; i++){ mask1 <<= 1; if(i < pos - 1){ mask1 |= 1L; } } long mask2 = 0; for(int i = 0; i < length; i++){ mask2 <<= 1; if(i >= pos -1){ mask2 |= 1L; } } long tmp1 = (mask1 & seq) | ((mask2 & seq) >> 1); seq = tmp1 | (1L << length - pos); return seq; } private static int countBits(long seq, long parityBit, int length) { long mask = 0; for(long i = 0; i <= length; i++){ mask <<= 1; if((i & parityBit) != 0){ mask |= 1L; } } return Long.bitCount(seq & mask) - 1; } }
 import static org.junit.Assert.*; import org.junit.*; public class UTest { @Test(timeout = 100) public void testCalcBasic1() { long bitSequence = Long.parseLong("1010110", 2); long res = Solution.calcHamming(bitSequence, 7, true); assertEquals(0b01110100110, res); } @Test(timeout = 100) public void testCalcBasic2() { long bitSequence = Long.parseLong("1010110110001", 2); long res = Solution.calcHamming(bitSequence, 13, true); assertEquals(0b101101001101100101, res); } @Test(timeout = 100) public void testCalcBasic3() { long bitSequence = Long.parseLong("1010", 2); long res = Solution.calcHamming(bitSequence, 4, false); assertEquals(0b0110010, res); } @Test(timeout = 100) public void testCalcBasic4() { long bitSequence = Long.parseLong("1", 2); long res = Solution.calcHamming(bitSequence, 1, true); assertEquals(0b111, res); } @Test(timeout = 100) public void testCheckBasic1() { long bitSequence = Long.parseLong("110111010001", 2); long res = Solution.checkHamming(bitSequence, 15, false); assertEquals(0b000110111011001, res); } @Test(timeout = 100) public void testCheckBasic2() { long bitSequence = Long.parseLong("101101001001100101", 2); long res = Solution.checkHamming(bitSequence, 18, true); assertEquals(0b101101001101100101, res); } @Test(timeout = 100) public void testCheckBasic3() { long bitSequence = Long.parseLong("110011", 2); long res = Solution.checkHamming(bitSequence, 7, false); assertEquals(0b0110010, res); } @Test(timeout = 100) public void testCheckBasic4() { long bitSequence = Long.parseLong("110", 2); long res = Solution.checkHamming(bitSequence, 3, true); assertEquals(0b111, res); } @Test(timeout = 100) public void testCheckBasic5() { long bitSequence = Long.parseLong("0110010", 2); long res = Solution.checkHamming(bitSequence, 7, false); assertEquals(0b0110010, res); } }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.