https://web.stanford.edu/class/archive/cs/cs107/cs107.1174/assign4/#2-sudoku-sets

2. Sudoku sets

Treating an unsigned type as a bit vector can compactly represent and efficiently manipulate a set over a given range. Bit vectors are used in time and space-constrained situations to provide dense storage and allow fast manipulation of the entire group of bits at once. In a bit vector, each individual bit is designated to represent a particular value and a bit is turned on to indicate its corresponding value is contained in the set. In this problem, we have sets drawn from the range [1-9]. A set is represented using an unsigned short (16 bits). The bit at the nth position (counting from least significant bit at the 0th position) is designated to represent the value n. The bits in the positions 1 to 9 represent the set membership and the other seven bits of the short are ignored. Below is a few example sets and their corresponding bit vectors. The bit positions 1 to 9 are shown in blue to distinguish them from the unused bits around them.

0000000000000000 // {} 0000001010100100 // {2 5 7 9} 0000000000001110 // {1 2 3} 

Write the make_set function to create a bit vector set from an array. The arguments to the function are an array of integer values and the array count. The function returns an unsigned short that represents a bit vector set of the values from the array. The bits in positions 1-9 of the returned result mark the set membership, the remaining bits are zeros. You may assume that no value in the array will be outside the range 1-9.

unsigned short make_set(int values[], int nvalues) 

Now write the is_single function to manipulate these bit vector sets in efficiently computing a result needed when solving a Sudoku puzzle. The goal of Sudoku is to assign every cell in the grid a digit from 1 to 9 subject to the constraint that each digit can be used only once in each row, column, and block. (You can read about Sudoku in wikipedia if you're curious, but for the purposes of this problem, you don't need to know any more details). The is_single function is given three well-formed bit vector sets representing the digits already used in the row, column, and block for a cell. ("well-formed" means that the short will have bits on only in positions 1-9, remaining bits are zeros). The possibilities for a cell consist of only those digits that are unused; any digit that is already used in the row, column, or block is not a possibility. The function is_single returns true if the already used digits force only one option for this cell (number of possibilities is exactly 1) and false otherwise (i.e. number of possibilities is 0 or 2 or more).

bool is_single(unsigned short used_in_row, unsigned short used_in_col, unsigned short used_in_block) 

The ideal implementation of is_single builds on direct and efficient use of bitwise operators (~ & ^ | << >>) with very limited use of the integer arithmetic/relational operators and is expressed in straight-line code (i.e., no loops, no if/switch, no chain of essentially same operation repeated 8-9 times and joined with some connective operator). If you can't quite achieve the ideal, a working solution that is unnecessarily awkward/inefficient can still earn most of the credit.