BitMask operation in java

Question

Consider the scenario I have values assigned like these

Amazon -1

Walmart -2

Target -4

Costco -8

Bjs -16

In DB, data is stored by masking these values based on their availability for each product. eg.,

Mask product description

1 laptop Available in Amazon

17 iPhone Available in Amazon and BJ

24 Mattress Available in Costco and BJ's

Like these all the products are masked and stored in the DB.

How do I retrieve all the Retailers based on the Masked value., eg., For Mattress the masked value is 24. Then how would I find or list Costco & BJ's programmatically. Any algorithm/logic would be highly appreciated.

Answer 1

int mattress = 24;
int mask = 1;
for(int i = 0; i < num_stores; ++i) {
    if(mask & mattress != 0) {
        System.out.println("Store "+i+" has mattresses!");
    }
    mask = mask << 1;
}

The if statement lines up the the bits, if the mattress value has the same bit as the mask set, then the store whose mask that is sells mattresses. An AND of the mattress value and mask value will only be non-zero when the store sells mattresses. For each iteration we move the mask bit one position to the left.

Note that the mask values should be positive, not negative, if need be you can multiply by negative one.

Answer 2

Assuming you mean in a SQL database, then in your retrieval SQL, you can generally add e.g. WHERE (MyField AND 16) = 16, WHERE (MyField AND 24) = 24 etc.

However, note that if you're trying to optimise such retrievals, and the number of rows typically matching a query is much smaller than the total number of rows, then this probably isn't a very good way to represent this data. In that case, it would be better to have a separate "ProductStore" table that contains (ProductID, StoreID) pairs representing this information (and indexed on StoreID).

Answer 3

Are there at most two retailers whose inventories sum to the "masked" value in each case? If so you will still have to check all pairs to retrieve them, which will take n² time. Just use a nested loop.

If the value represents the sum of any number of retailers' inventories, then you are trying to trying to solve the subset-sum problem, so unfortunately you cannot do it in better than 2^n time.

If you are able to augment your original data structure with information to lookup the retailers contributing to the sum, then this would be ideal. But since you are asking the question I am assuming you don't have access to the data structure while it is being built, so to generate all subsets of retailers for checking you will want to look into Knuth's algorithm [pdf] for generating all k-combinations (and run it for 1...k) given in TAOCP Vol 4a Sec 7.2.1.3.