Last active
September 25, 2018 08:10
-
-
Save vhain/c12be376024ca405580cc5524f0cf250 to your computer and use it in GitHub Desktop.
int array to long encode/decode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.*; | |
class LongEncoder { | |
/** | |
* Returns long including all int[] values. | |
* | |
* @param values integer array to encode | |
* @param offset bit offset for each value. should meet criteria | |
* values.length * offset <= 64 which is maximum of long. | |
* e.g. using offset as 20 is good for range 0-1048575 | |
* @return encoded long value | |
*/ | |
private static long encode(int[] values, int offset) { | |
assert values.length * offset <= 64 : "values length overflow"; | |
long result = 0; | |
// each value should not exceed offset bits | |
long maxValue = (long)Math.pow(2, offset); | |
for (int i = 0; i < values.length; i += 1) { | |
// make sure value is good | |
assert values[i] < maxValue : "value overflowed maxValue"; | |
assert values[i] >= 0 : "value should not be negative"; | |
// up-scale (multiply but using bitwise) for each region defined by offset | |
long val = (long)values[i] << (i * offset); | |
result += val; | |
} | |
return result; | |
} | |
/** | |
* Returns int[] decoded from long value encoded by encode(). | |
* | |
* @param value encoded long value | |
* @param length original length of int[] values | |
* @param offset original offset used while calling encode(). | |
* @return decoded int[] | |
*/ | |
private static int[] decode(long value, int length, int offset) { | |
int[] result = new int[length]; | |
// calculate region of interest | |
long roi = (long)Math.pow(2, offset) - 1; | |
for (int i = 0; i < length; i += 1) { | |
// extract (modular but using bitwise) interested part for index with roi | |
// and down-scale (divide but using bitwise) into original value | |
result[i] = (int)(((roi << (offset * i)) & value) >> (offset * i)); | |
} | |
return result; | |
} | |
/** | |
* Run test for int[] values | |
* | |
* @param values int[] values to test with | |
*/ | |
private static void test(int[] values) { | |
System.out.print("testing for values = [ "); | |
for (int i = 0; i < values.length; i += 1) { | |
System.out.print(String.format("%d, ", values[i])); | |
} | |
System.out.print("] - "); | |
long v = LongEncoder.encode(values, 20); | |
int[] result = LongEncoder.decode(v, values.length, 20); | |
for (int i = 0; i < result.length; i += 1) { | |
assert result[i] == values[i] : "test case failed"; | |
} | |
System.out.println("test ok"); | |
} | |
private static void testSuite() { | |
// test max value | |
test(new int[]{1048575, 1048575, 1048575}); | |
// test edge case: 0 | |
test(new int[]{0, 0, 0}); | |
// some more test cases | |
test(new int[]{1, 1, 1}); | |
test(new int[]{1, 1048575, 1}); | |
test(new int[]{1048575, 0, 1048575}); | |
} | |
public static void main(String[] args) { | |
LongEncoder.testSuite(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment