Krasimir Yordzhev

Faculty of Natural Sciences
South-West University “Neofit Rilski”
Blagoevgrad Bulgaria
E-mail: yordzhev@swu.bg

Резюме. This article is intended for anyone who studies programming, as well as for his teachers. The article deals with the some aspects of teaching programming languages C++ and Java. It presents some essential and interesting examples of the advantages of using bitwise operations to create efficient algorithms in programming. Particular attention is paid to the entertaining task of writing a program receiving Latin squares of arbitrary order.

Ключови думи: bitwise operations; binary notation; set; Latin square

1. Introduction

The present study is thus especially useful for students educated to become programmers as well as for their lecturers. In the article we present some meaningful examples for the advantages of using bitwise operations for creating effective algorithms. To implement the algorithm, we will use essentially bitwise operations.

The use of bitwise operations is a powerful means during programming with the languages C/C++ and Java. Some of the strong sides of these programming languages are the possibilities of low-level programming. Some of the means for this possibility are the introduced standard bitwise operations, with the help of which it is possible directly operating with every bit of an arbitrary variable situated in the computer memory . Unfortunately , in the widespread books, the topic on effective using of bitwise operations is incomplete or missing. The aim of this article is to correct this lapse to a certain extent and present some meaningful examples 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. For a deeper study of this subject, we recommend the book [Yordzhev, 2019].

For more details see, for example, in [Davis, 2014, Kernighan and Ritchie, 1998, Todorova, 2002a, T odorova, 2002b] for C/C++ programming languages and in [Evans and Flanagan, 2015, Hadzhikolev and Hadzhikoleva, 2016, Schildt, 2014, Schildt, 2017] for Java programming language. In section 2 we will only recall the definitions of the basic concepts.

2. Bitwise operations – basic definitions

The bitwise operations apply only to integer data type, i.e. they cannot be used for float and double types.

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 \(\mathrm{x}, \mathrm{y}\) and z be integer variables or constants of one type, for which \(w\) bits are needed. Let x and y be initialized (if they are variables) and let the assignment z \(=\mathrm{x} \& \mathrm{y}\); (bitwise AND), or \(\mathrm{z}=\mathrm{x} \mid \mathrm{y}\); (bitwise inclusive OR), or \(\mathrm{z}=\mathrm{x}{ }^{\wedge} \mathrm{y}\); (bitwise exclusive \(O R\) ), or \(\mathrm{z}=\sim \mathrm{x}\); (bitwise NOT) be made. For each \(i=0,1,2, \ldots, w-1\) \(i=0,1,2, \ldots, w-1\), the new contents of the \(i\)-th bit in z will be as it is presented in the Table 1.

In case that k is a nonnegative integer , then the statement \(\mathrm{z}=\mathrm{x} \ll \mathrm{k}\) (bitwise shift left) will write (\(i+k\) ) in the bit of z the value of the \(k\) bit of x, where \(i=0,1, \ldots, 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 \(\mathrm{z}=\mathrm{x} \gg \mathrm{k}\) (bitwise shift right) works in a similar way . However, we must be careful if we use the programming language C or \(\mathrm{C}++\), as in various programming environments (see for example in [Glushakov et al., 2001]), this operation has different interpretations. Somewhere \(k\) bits of z from the very left place are by requirement 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 types 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: \(\mathrm{z}=\mathrm{x} \gg \mathrm{k}\) and \(\mathrm{z}=\mathrm{x} \ggg \mathrm{k}\) [Evans and Flanagan, 2015, Schildt, 2017].

Bitwise operations are left associative.

The priority of operations in descending order is as follows:

• – ~ (bitwise NOT);

• – the arithmetic operations * (multiply), / (divide) and % (remainder or modulus);

• – the arithmetic operations + (addition) and – (subtraction);

• – the bitwise operations << and >>;

• – the relational operations <, >, <= and >=;

• – the relational operations \(==\) and !=;

• – the bitwise operations &,| and ^;

• – the logical operations && and ||.

Example 1. Directly form the definition of the operation bitwise shift left follows the effectiveness of the following function computing \(2^{k}\), where \(k\) is a nonnegative integer:

Example 2. To divide the integer \(x\) into \(2^{S}\) by cutting the remaining of the result (the ”remainder” operation \(f(x)=x \%\left(2^{n}\right)\) ), we can take advantage of the C++ function:

Example 3. To compute the value of the \(i\)-th bit (0 or 1) in computer presentation of a nonnegative integer variable \(x\) we can use the function:

3. Bitwise operations in relation to the binary representation of integers In order to understand all the possibilities of bitwise operations, there is a need for a solid knowledge of the notion of ” number system”. The great applications of different number systems and most of all the binary system for representation of integers in computer science and in programming are well known. The main features of this concept are studied in secondary schools and universities. In these courses, the representation of integers in different number systems is studied in detail. In computer science and programming, it is particularly important to present the integers in binary notation (binary number system).

Example 4. The next function prints an integer in binary notation. We do not consider and we do not print the sign of integer. For this reason, we work with \(|n|\) (absolute value, or module of integer \(n\) ).

Example 5. The following function calculates the number of 1’s in the binary notation of an integer n. Again, we ignore the sign of the number.

When working with negative numbers, we have to take into account that computer presentation of negative numbers became a special way. How to represent the integers of type short can be seen from Example 6, where we essentially use bitwise operations. The function that we will describe is a modification of the function from Example 4.

Example 6. Function showing the representation of the integers of type short in the computer’s memory.

Some experiments with the function BinRepl(short) are given in Table 2. 4. The bitwise operations and sets

Let \(n\) be a positive integer. In the present work we will only consider values of \(n\), such that \(1 \leq n \leq\)"sizeof(long)"*8-1, where sizeof(long)=4 for C++ programming language and sizeof(long)=8 for Java programming language. Throughout \(\mathcal{U}\) denotes the set \[ \mathcal{U}=\{1,2, \ldots, n\} . \]

Let \(A \subseteq \mathcal{U} A \subseteq \mathcal{U}\). We denote by \(\mu_{i}(A)\) the functions

(1)\[ \mu_{i}(A)=\left\{\begin{array}{ll} 1 & \text { if } \quad i \in A \\ 0 & \text { if } \quad i \notin A \end{array}, \quad i=1,2, \ldots .\right. \]

Then the set \(A\) can be represented uniquely by the integer

(2)\[ v(A)=\sum_{i=1}^{n} \mu_{i}(A) 2^{i-1}, \quad 0 \leq v(A) \leq 2^{n}-1, \]

where \(\mu_{i}(A), i=1,2, \ldots, n\) is given by formula (1). In other words, each subset of \(U\), we will represent uniquely with the help of an integer from the interval \(\left[0,2^{n}-1\right]\) (integer representation of sets).

It is readily seen that

(3)\[ v(\mathcal{U})=2^{n}-1 \]

Evidently if \(A=\{a\}\), i.e. \(|A|=1\), then

(4)\[ v(\{a\})=2^{a-1} \]

The empty set \(\varnothing\) is represented by

(5)\[ v(\emptyset)=0 . \]

The expressions, that represent operations with sets, we will use in the next section 5 for a description of the algorithm to obtain a random exponential Latin square.

1. According to equation (3), the set \(\mathcal{U}=\{1,2, \ldots n\}\) is represented by the equation \[ U=(1 \ll n)-1 \]

2. According to equation (4), a singleton \(A=\{a\} \subset \mathcal{U}\) is represented by the equation

\[ A=1 \ll(a-1) \]

3. Let \(A\) and \(B\) be two integers, which represent two subsets of \(\mathcal{U}\). Then the integer \(C\) that represents their union is represented by the equation

\[ C=A \mid B \]

4. Let \(A \subseteq B\). Then, to remove all elements of \(A\) from \(B\), we can do it with the help of the equation

\[ \mathrm{B}^{\wedge} \mathrm{A} . \]

In programming languages \(\mathrm{C} / \mathrm{C}++\) and Java there is no standard type"set" and standard operations with sets [Todorova, 2011]. In this case we have to look for additional instruments to work with sets - for example the associative containers set and multiset realized in Standard Template Library (STL) [Azalov, 2008, Collins, 2003, Horton, 2015, Lischner , 2009, W ilson, 2007]. It can be used the template class set of the system of computer algebra ”Symbolic C++”, programming code is given in details in [Tan et al., 2000]. Of course we can be built another class set, and specific methods of this class can be described, as a training. This is a good exercise for the students, when the cardinal number of the basic (”universal”) set \(\mathcal{U}\) is not very big. Below we give the solution of this task using bitwise operations [Kostadinova and Yordzhev, 2011, Yordzhev, 2018a].

Example 7. The class Set_N describes construction and operations with sets of integers by means of overloading of operators and using bitwise operations:

5. An entertainment example – algorithm to obtain a random Latin square using bitwise operations

A Latin square of order \(n\) is a \(n \times n\) matrix where each row and column is a permutation of elements of the set \(\{1,2, \ldots, n\}\). Thus far it is known the number of all Latin squares of order \(n\), where \(n \leq 11\) [McKay and Wanless, 2005, Sloane, 2019].

Latin squares and hypercubes have their applications in coding theory , error correcting codes, information security , decision making, statistics, cryptography , conflict-free access to parallel memory systems, experiment planning, tournament design, enumeration and study of H-functions, etc [Kovachev, 2011, Laywine and Mullen, 1998].

A special kind of Latin squares are the Sudoku-matrices [Yordzhev, 2018b].

Definition. [Yordzhev, 2016] A matrix \(M_{n \times n}=\left(\alpha_{i j}\right)_{n \times n}\) is called an exponential Latin square of order \(n\) if the following condition hold:

1. For every \(i, j \in\{1,2, \ldots, \mathrm{n}\}\) there exists \(k \in\{1,2, \ldots, \mathrm{n}\}\), such that \(\alpha_{i, j}=2^{k}\);

2. The matrix \(M_{n \times n}{ }^{\prime}=\left(\log _{2} \alpha_{i j}\right)_{n \times n}\) is a Latin square of order \(n\).

If \(n\) is a positive integer, then it is readily seen that the set of all \(n \times n\) Latin squares and the set of all \(n \times n\) exponential Latin squares are isomorphic.

In this section we will show that it is easy to create an algorithm for generating random exponential Latin squares of order \(n\) using bitwise operations. The presentation of the subsets of the set \(\mathcal{U}=\{1,2, \ldots n\}\) using the formula (2) and the convenience in this case to work with bitwise operations are the basis of algorithm described by us. Some other algorithms for obtaining random Latin squares and random Sudoku matrices and their valuation are described in detail in [DeSalvo, 2017, Fontana, 2011, Yordzhev, 2012, Yordzhev, 2016].

Example 8. A program code for obtaining \(N \times N\) random Latin squares:

With the help of algorithm described in Example 8, we received a lot of random exponential Latin squares, for example the next one of order 12:

REFERENCES

Azalov, P. (2008). Object-oriented programming. Data structures and STL. Ciela, Sofia. (in Bulgarian)

Collins, W. (2003). Data structures and the standard template library. McGraw-Hill, New York.

Davis, S. R. (2014). C++ for Dummies. John Wiley & Sons, N.J., 7 edition.

DeSalvo, S. (2017). Exact sampling algorithms for latin squares and sudoku matrices via probabilistic divide-and-conquer. Algorithmica, 79(3): 742 – 762.

Evans, B. J. and Flanagan, D. (2015). Java in a Nutshell. O’Reilly, 6 edition.

Fontana, R. (201 1). Fractions of permutations. an application to sudoku. Journal of Statistical Planning and Inference, 141(12): 3697 – 3704.

Glushakov, S. V., Koval, A. V. and Smirnov, S. V. (2001). The C++ Programming Language. Folio, Kharkov. (in Russian)

Hadzhikolev, E. and Hadzhikoleva, S. (2016). Fundamentals of programming with Java. University Publishing House ”Paisiy Hilendarski”, Plovdiv , (in Bulgarian).

Horton, I. (2015). Beginning STL: Standard Template Library. Apress.

Kernighan, B. W. and Ritchie, D. M. (1998). The C programming Language. AT&T Bell Laboratories, N.J., 2 edition.

Kostadinova, H. and Yordzhev, K. (201 1). An entertaining example for the usage of bitwise operations in programming. In Proceedings of the Fourth International Scientific Conference – FMNS2011, volume 1, pages 159–168, Blagoevgrad, Bulgaria. SWU “N. Pilsky”.

Kovachev, D. S. (2011). On some classes of functions and hypercubes. Asian-European Journal of Mathematics, 4(3):451 – 458.

Laywine, C. F . and Mullen, G. L. (1998). Discrete Mathematics Using Latin Squares. Wiley Series in Discrete Mathematics and Optimization (Book 49). John Wiley & Sons, New York.

Lischner, R. (2009). STL Pocket Reference. O’Reilly Media.

McKay, B. D. and Wanless, I. M. (2005). On the number of latin squares. Annals of Combinatorics, 9(3):335 – 344.

Schildt, H. (2014). Java: The Complete Reference. McGraw-Hill, 9 edition.

Schildt, H. (2017). Java: A Beginner’s Guide. McGraw-Hill, 7 edition.

Sloane, N. J. A. (2019). A002860 – number of latin squares of order \(n\); or labeled quasigroups. The On-Line Encyclopedia of Integer Sequences (OEIS). http://oeis.org/A268523, Last accessed on 9 April 2016.

Tan, K. S., Steeb, W.-H., and Hardy, Y. (2000). Symbolic C++: An Introduction to Computer Algebra using Object-Oriented Programming. Springer-Verlag, London.

Todorova, M. (2002a). Programming in \(C++\), volume 1. Ciela, Sofia (in Bulgarian).

Todorova, M. (2002b). Programming in \(C++\), volume 2. Ciela, Sofia (in Bulgarian).

Todorova, M. (201 1). Data structures and programming in \(C++\). Ciela, Sofia (in Bulgarian).

Wilson, M. D. (2007). Extended STL: Collections and iterators. Extended STL. Addison-Wesley.

Yordzhev, K. (2012). Random permutations, random sudoku matrices and randomized algorithms. International Journal of Mathematical Sciences and Engineering Applications, 6(VI): 291 – 302.

Yordzhev, K. (2016). Bitwise operations in relation to obtaining latin squares. British Journal of Mathematics & Computer Science, 17(5): 1 – 7.

Yordzhev, K. (2018a). The bitwise operations in relation to the concept of set. Asian Journal of Research in Computer Science, 1(4): 3072 – 3079.

Yordzhev, K. (2018b). How does the computer solve sudoku - a mathematical model of the algorithm. Mathematics and informatics, 61(3): 259 – 264 (in Bulgarian, abstract in English).

Yordzhev, K. (2019). Bitwise Operations and Combinatorial Applications. LAP Lambert Academic Publishing.