Thursday, October 11, 2007

Java data validation trick with bit-twiddling

I have a specialized value object with the property that fields can be null but only in a particular order:

class Data {
    private final String field1;
    private final String field2;
    private final String field3;

    public Data(String field1, String field2,
            String field3) {
        if (!valid(field1, field2, field3))
            throw new IllegalArgumentException();

        this.field1 = field1;
        this.field2 = field2;
        this.field3 = field3;
    }

    // ...
}

The rule is simple: Given the order of the fields 1-4, any later field may be null provided that no earlier field is null. That is, "abc", "def", null is ok but "abc", null, "ghi" is invalid.

So the question becomes, How to code up valid?.

The straight-forward approach of nested if-else blocks becomes particularly unwieldy as more fields are added. But it turns out there is a clever solution using bit-twiddling:

private static boolean valid(String... fields) {
    byte flag = 0; // Fails after 8 fields

    // Sets the i-th bit for each non-null field
    for (int i = 0; i < fields.length; ++i)
        if (null != fields[i])
            flag |= (1 << i);

    // Math trick: 2n ∧ 2n-1 = 0
    return 0 == (flag & flag + 1);
}

In words: the flag has a 1-bit for each non-null field in argument order. The validation condition only holds when the 1 bits are in sequence starting at the 0-th position with no gaps, e.g., 00000111. That particular bit pattern is the same as one less than some power of two. Use the math fact that in bit arithmetic, 2n ∧ 2n-1 = 0 to check the condition.

Thanks to this powers-of-two problem for pointing the way.

4 comments:

Alex Miller said...

Not sure, but use of BitSet might make this code clearer.

Brian Oxley said...

I looked into BitSet but it does not provide what I need to use the powers-of-two trick.

Anonymous said...

This should do same without bitfields and it does not fail with more than eight fields:

private static boolean valid2(String... fields) {
boolean nullFound = false;
for (String field : fields) {
if (field == null) {
nullFound = true;
}
else if (nullFound) {
return false;
}
}
return true;
}

Anonymous said...

And doesn't need modifications for greater amount of fields eather.