Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.