Count all X-shaped bits from 8 integers

Question

I am given 8 positive 32-bit integer numbers. The task is to write program to count all X-bits.

X-bits are groups of 9 bits (3 rows x 3 columns) forming the letter "X". task is to count all X-bits and print their count on the console. Valid X-bits consist of 3 numbers where their corresponding bit indexes are exactly {"101", "010", "101"}. All valid X-bits can be part of multiple X-bits (with overlapping).

Expected input and output:

Bellow is my solution, for any of the inputs it prints out the correct value, and it passes every test in our judge system, which makes me think that it's a valid solution to the problem. The idea of my approach is simple, the array is treated as if it was a 2d array and each group of 9 bits across 3 ints of the array is compared to the required pattern.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        int xCount = 0;
        int nums[] = new int[8];
        for(int i = 0; i < nums.length; i++) {
            nums[i] = Integer.parseInt(stdin.nextLine());
        }
        for (int i = 0; i < nums.length - 2; i++) { // nums.length - 2 because in validX(...) we have index (passed as i) + 2
            for (int j = 0; j < 29; j++) {              // 31 (index of the leftmost bit) - 2 because we have startingPosition + 2
                if(validX(nums, i, j) == true) {
                    xCount++;
                }
            }
        }
        System.out.println(xCount);
    }

    public static int get_bit(int num, int pos) {
        return ((num >> pos) & 1);
    }
    public static boolean validX(int nums[], int index, int startingPosition) {
        if(get_bit(nums[index], startingPosition) == 1 && get_bit(nums[index], startingPosition + 1) == 0
        && get_bit(nums[index], startingPosition + 2) == 1 &&
                get_bit(nums[index + 1], startingPosition) == 0 && get_bit(nums[index + 1], startingPosition + 1) == 1
                && get_bit(nums[index + 1], startingPosition + 2) == 0 &&
        get_bit(nums[index + 2], startingPosition) == 1 && get_bit(nums[index + 2], startingPosition + 1) == 0 &&
        get_bit(nums[index + 2], startingPosition + 2) == 1) {
            return true;
        }
        return false;
    }
    /*
     * in actuality what this function is doing is getting each individual bit and comparing it to the pattern
     * we need, which is:
     * {"101",
     *  "010",
     *  "101"}
     */
}

The issue I have with this code is that it's ugly. Truth be told I'm slightly ashamed of my validX(...) method, but I can't think of a quicker way or one that would take even less memory. The idea of my approach is simple, the array is treated as if it was a 2d array and each group of 9 bits is compared to the required pattern.

And just to get a few things out of the way, nobody assigned me this problem, I'm doing it to get better in Java. Whatever code I receive (if any at all) won't be submitted anywhere. Quite frankly I'm interested to know if there's a more elegant, readable solution which avoids hardcoded values. The reason I'm not happy with the default solution is because I don't think 0.2 s allowed runtime and 16 MB allowed memory is adequate for a problem like this.

Answer 1

I think the main issue is that you took a bit-by-bit approach to a problem that seems to be designed to elicit approaches that take advantage of bitwise operations, which made the solution less elegant(?) than intended. There is a lot of code to extract individual bits and testing them, and an extra loop to go over the startingPosition, and we can do away with that. I don't expect a performance problem with your solution though, 0.2 seconds is a ton of time (running literally a billion instructions in that time is not unreasonable) and barely any memory is allocated.

As you already discovered, the question of "is there an X here" can be answered by ANDing together the bits that make up the X and also ANDing that with the complements of the bits at the positions that must be zero. Rather than working with booleans, we could work with entire 32bit masks at once, and get an entire 32bit mask as a result, which will then indicate the positions where an X is found. The Xs that are present can be counted using Integer.bitCount.

Forming that mask is really the same idea as the code you already wrote, but instead of adding offsets to the startingPosition there will be some bit-shifts. For example:

private static int calculateXMask(int top, int middle, int bottom) {
    return (top >>> 1) & ~top & (top << 1) &
        (~middle >>> 1) & middle & (~middle << 1) &
        (bottom >>> 1) & ~bottom & (bottom << 1);
}

Which can then be applied to every "window" of 3 successive integers in num, with the results bitCounted and added up.

Answer 2

Well. It's ugly because of the unnecessary if statement. And if you re-format your code, it's not as ugly anymore, and directly clear what it does:

public static boolean validX(int nums[], int index, int startingPosition) {

    return (   get_bit(nums[index]     , startingPosition    ) == 1 && 
               get_bit(nums[index]     , startingPosition + 1) == 0 &&
               get_bit(nums[index]     , startingPosition + 2) == 1 &&
               get_bit(nums[index + 1] , startingPosition    ) == 0 && 
               get_bit(nums[index + 1] , startingPosition + 1) == 1 &&
               get_bit(nums[index + 1] , startingPosition + 2) == 0 &&
               get_bit(nums[index + 2] , startingPosition    ) == 1 && 
               get_bit(nums[index + 2] , startingPosition + 1) == 0 &&
               get_bit(nums[index + 2] , startingPosition + 2) == 1) ;

}

This might not be as fast as needed, but (IMHO) much better readable.

If you need raw speed, you could generate a (8x32)=256 bit BitSet and a BitSet of the mask. You can then just linearly slide that mask over the input bitset and and() them. Check the bits that are left true with BitSet#cardinality().