Bitwise Operations Related to a Combinatorial Problem on Binary Matrices

Published Online May 2013 in MECS DOI: 10.5815/ijmecs.2013.04.03

The present study is thus especially useful for students educated to become programmers as well as for their lecturers. A meaningful example for the advantages of using bitwise operations for creating effective algorithms in programming is presented in this article. We will consider an open combinatorial problem on binary matrices and its solution using the algorithm for some values of the integer parameters n and к . To implement the algorithm, we will use essentially bitwise operations.

The use of bitwise operations is a powerful method used in C/C++ and Java programming languages. Unfortunately, in the widespread books on this topic there is incomplete or no description for the work of the bitwise operations. The aim of this article is to correct this lapse to a certain extent and present a meaningful example of a programming task, where the use of bitwise operations is appropriate in order to facilitate the work and to increase the effectiveness of the respective algorithm.

This work is an extension and complement to [1].

A binary (or boolean , or (0,1)- matrix ) is a matrix whose all elements belong to the set В = {0,1}. With B_n we will denote the set of all n x n binary matrices.

Some algorithms for isomorphism-free generations of combinatorial objects are discussed in detail in [2]. In our work we will consider a problem of this type. Its formulation is as follows: A set of binary matrices £ c B_n is given. In £ is defined an equivalence relation.

An algorithm which did not study every element of the set £, and which receives one representative of each equivalence class to be described. For this purpose, we will use significantly bitwise operations.

In Section II we formulate the problem and we give some well known results. In Section IV we will describe in detail an algorithm for computer solution of the formulated problem. Section III is only for reference.

• II.    Preliminaries and problem formulation

Let n and к be positive integers. We let Л* П denote the set of all n x n binary matrices in each row and each column of which there are exactly к in number 1's. Let us denote with

A(n, к) = |Л П |                                    (1)

the number of all elements of Ain .

There is not any known formula to calculate the A(n, к) for all n and к . There are formulas for the calculation of the function A(n, к) for each n for relatively small values of к; more specifically, for к = 1, к = 2 and к = 3. We do not know any formula to calculate the function A(n, к) for к > 3 and for all positive integer n.

It is easy to prove the following well-known formula

A(n, 1) = n!

The following formula

B(n, 2) = y,2x2+3x3+-+nxn =n np_2xr !(2г)хт is well known [3].

One of the first recursive formulas for the calculation of A(n, 2) appeared in [4] (see also [5, p. 763]).

Л(1,2) = 0,  A(2,2) = 1,  A(3,2) = 6;(4)

for n > 4,

A(n, 2) = 1 n(n - 1)2[(2n - 3)A(n - 2,2) + (n -2)2B(n - 3,2)](5)

Another recursive formula for the calculation of Л (и, 2) occurs in [6].

Л(1,2) — 0 , Л(2,2) — 1 ;                        (6)

for и > 3

Л(и, 2) = (и - 1)иЛ(и - 1,2) + ^(и-1^)2и Л(и - 2,2)

The next recursive system is to calculate Л(и, 2):

Л(1,2) = 0, Л(2,2) = 1,(8)

for и > 2

Л(и + 1,2) = и(2и - 1)Л(и, 2) + и2Л(и - 1,2) -и (и + 1);(9)

и(1) = и(2) = и(3) = 0, и(4) = 9;(10)

for и > 4

и(и + 1) = (и - 1)24[8(и - 2)(и - 3)Л(и - 2,2 + (и - 2)2Л(и - 3,2) - 4и(и - 1)](11)

where и (и) identifies the number of a special class of Л и -matrices [7].

The following formula is an explicit form for the calculation of Л(и, 3).

з,      - иЛ' (-1)^ ^ +3^) ^!2 “ 3 ^

^Л(и,³⁾ - ^и! —    . —,            ⁽¹²⁾

where the sum is done as regards all ^(и+2)(и+1) solutions in nonnegative integers of the equation a + ^ + у — и [8]. As it is noted in [9], the above formula does not give us good opportunities to study behavior of Л(и, 3).

Let Л, S E A ^ . We will say that Л: S, if Л is obtained from S by moving some rows and/or columns. Obviously, the relation defined like that is an equivalence relation. We denote with

к(и,к) — |ди д |                             (13)

the number of equivalence classes on the above defined relation.

Problem 1 Find ^(и, к) for given integers и and к, 1 < к < и .

The task of finding the number of equivalence classes for all integers и and к, 1 < к < и is an open scientific problem. We partially solve this problem by making a computer program to find this number for some (not great) values of и and к . Moreover, using bitwise operations, our algorithm will receive one representative from each equivalence class without examining the whole set A ^ .

• III.    Bitwise operations

Bitwise operations can be applied for integer data type only, i.e. they cannot be used for float and double types. For the definition of the bitwise operations and some of their elementary applications could be seen, for example, in [10, 11, 12].

We assume, as usual that bits numbering in variables starts from right to left, and that the number of the very right one is 0.

Let x,y and z are integer variables or constants of one type, for which bits are needed. Let x and y are initialized (if they are variables) and let the assignment z = x & y; ( bitwise AND ), or z = x | y; ( bitwise inclusive OR ), or z = x ^ y; ( bitwise exclusive OR ), or z = ~x;

( bitwise NOT) be made. For each i — 0,1,2, ..., w - 1, the new contents of the i -th bit in z will be as it is presented in the Table I.

TABLE I.

Bitwise operations

i-th bit of x	i-th bit of y	i-th bit of z = x & y;	i-th bit of z = x | y;	i-th bit of z = x ^ y;	i-th bit of z = ~x;
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	0
1	1	1	1	0	0

In case that k is a nonnegative integer, then the statement z = x<bitwise shift left) will write ( i + k) in the bit of z the value of the k bit of x, where i = 0,1, ... ,w — k — 1, and the very right k bits of x will be filled by zeroes. This operation is equivalent to a multiplication of x by 2^k.

The statement z=x>>k ( bitwise shift right ) works the similar way. But we must be careful if we use the programming language C or C++, as in various programming environments this operation has different interpretations - somewhere k bits of z from the very left place are compulsory filled by 0 (logical displacement), and elsewhere the very left k bits of z are filled with the value from the very left (sign) bit; i.e. if the number is negative, then the filling will be with 1 (arithmetic displacement). Therefore it is recommended to use unsigned type of variables (if the opposite is not necessary) while working with bitwise operations. In the Java programming language, this problem is solved by introducing the two different operators: z=x>>k and z=x>>>k [12].

Bitwise operations are left associative.

The priority of operations in descending order is as follows: ~ (bitwise NOT); the arithmetic operations * (multiply), / (divide), % (remainder or modulus); the arithmetic operations + (addition) - (subtraction); the bitwise operations << and >>; the relational operations <, >, <=, >=, ==, !=; the bitwise operations &,^ and |;

To compute the value of the i -th bit of an integer variable x we can use the function:

int BitValue(int x, unsigned int i)

{ return ( (x & 1<

}

The next function prints an integer in binary notation. We don't consider and we don't print the sign of integer. f or this reason we work with | n | .

void DecToBin(int n)

{ n = abs(n);

int b;

int d = sizeof(int)*8 - 1;

while ( d>0 & (n & 1<<(d-1) ) == 0 ) d--;

while (d>=0)

{ b= 1<<(d-1) & n ? 1 : 0; cout<

d--;

}

}

The following function calculates the number of 1's in the binary representation of an integer n. Again we ignore the sign of the number.

int NumbOf_1(int n)

{ n = abs(n);

int temp=0;

int d = sizeof(int)*8 - 1;

for (int i=0; i

}

• IV.    Description and Implementation of the Algorithm

Let N be the set of natural numbers and let

Tn = «X1,X2, ... ,x„) | Xi E N, i = 1,2, ... ,n^}     (14)

An one to one corresponding

Ф ^:^n"^ Tn                                  ⁽¹⁵⁾

In [13], it is proved that the representation of the elements of Bn using ordered n -tuples of natural numbers leads to making a fast and saving memory algorithms.

Let A E Bn and let

X = (x^, ...,xn) = ^(A).(16)

Then we denote x6 = ф(At),(17)

where A6 E Bn is the transpose of the matrix A.

Let

X = (xt,x2, ... ,xn)(18)

and let

X6 = <У1,У2, ...,Уп).(19)

Then we will call x a canonical element, if x1

У1 < У2 <-<Ун .(21)

Proposition 1 There is un unique canonical element in every equivalence class of factor-set Л”,.

The proof of proposition 1 is within the reach of any student who has successfully studied the properties of the binary system concept and we will miss it here.

Proposition 1 is the base of our algorithm, which we describe in brief below. For its implementation, we will use also the functions shown in Section III.

As it is well known, there are exactly 2” nonnegative integers, which are presented with no more than ” digits in binary notation. We need to select all of them, which have exactly к 1's in binary notation. Their number is (”) « 2”. We could use the function NumbOf_1(int) from section 3, but then we have to use it for each integer from the interval [0,2” — 1], i.e. 2” times. We will describe an algorithm that directly receives the necessary elements without checking whether any integer m E [0,2” — 1] satisfies the conditions. We will remember the result in the array p[] of size c = Q). Moreover, the obtained array is sorted in ascending order and there are no duplicate elements. The algorithm is based on the fact that the set of all ordered m-tuples

®m = <61, 62.....6m), 6i E В = {0,1},(22)

i = 1,2, ..., m, m = 1,2, ..., ”, is partitioned into two disjoint subsets

Bm = Mt и М2, М1 n M2 = 0,(23)

where

and

{ if (k<=0)

{ c = 1;

p[0] = 0;

} else if (k==n)

{ c = 1;

p[0] = (1<2ⁿ -1

} else

{ int p1[10000], p2[10000];

int c1, c2;

DataNumb(p1, n-1, k, c1);

DataNumb(p2, n-1, k-1, c2);

c = c1+c2;

for (int i=0; i

p[i] = p1[i];

for (int i=0; i

p[c1+i] = p2[i] | 1<<(n-1);

}

}

We also will use bitwise operations in constructing the next two functions.

The function int n_tuple(int[], int, int, int) gets all t = ” + к 1) (combinations with repetitions) ordered ”-tuples 1,x₂, ..., X”), where 0 < X1< x₂< — < X”< c, x_i, i = 1,2, ..., ” are elements of sorted array p[] of size c. As a result, the function returns the number of canonical elements.

The function bool check(int[], int) refers to the use of each received ” -tuples. It examines whether this is a canonical element and prints it.

bool check(int x[], int n, int k)

{ int yj;     // the integer representing column (n-j)

int y0=0;    // integer preceding column j int b;

for (int j=n-1; j>=0; j--)

{ yj=0;

for (int i=0; i

{ b = 1<

} if (yj

}

// We have received a canonical element. Print it:

for (int i=0; i

cout<<'\n';

return true;

} int n_tuple(int p[], int n, int k, int c) { int t=0;

int a[n], x[n];

int indx = n-1;

for (int i=0; i

while (indx >= 0)

{ for (int i=indx+1; i

for (int i=0; i

if(check(x,n,k)) t++;

indx = n-1;

a[indx]++;

{ indx--;

a[indx]++;

}

} return t;

}

The description of the main function, we leave to the reader.

• V.    Conclusions

The number of equivalence classes for 1 < к < n< 9 are given in Table II, which is obtained through the work of the algorithms described in this paper.

The ideas described in this article can be used for finding the cardinality of other factor-sets of binary matrices

TABLE II

THE NUMBER OF EQUIVALENCE CLASSES FOR 1≤K<N≤9

n к	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1
2		1	2	5	13	42	155	636
3			1	3	25	272	4 070	79 221
4				1	5	161	7 776	626 649
5					1	8	1 112	287 311
6						1	13	8 787
7							1	21
8								1