You are here:

# C++/Bit Operators

Question
How can you tell whether the binary number of a character is odd or even.  I not sure I understand the bit operators.  I need to write a simple script that will ask the user to enter a character and then tell count the number of binary one and tell whether the number of one is odd or even.  just want some help with bit operator the rest I can figure out.  I know you will be using a loop but I keep getting the wrong value.

First you need to understand what you are being asked to do.

From your description of the question you are _not_ being asked whether the value of a character or an individual bit is odd or even but whether the number of bits in the character that are 1 is odd or even, thus:

'A' has the ASCII value 65, or 41 hexadecimal or 0100 0001 binary. The number of 1 bits in this character is 2 and thus 'A' gives an even result.

'1' has the ASCII value 49 or 31 hexadecimal or 0011 0001 binary. The number of 1 bits in this character is 3 and thus '1' gives an odd result.

Next you have to think how to count the number of bits in the character. You are correct when you say you will require a loop. Each time around the loop you have to add 1 to the count if the bit in question is 1 or 0 (or no change) if not. There are several ways you could do this, however you need to check only one bit each time. The operation to allow this is called a mask operation and is performed by using a bitwise AND operation. The Boolean AND operation has the following truth table (view using a fixed pitch font such as Courier):

Result = a AND b

a    b      Result
-------------------
0    0        0
0    1        0
1    0        0
1    1        1

That is both operands have to be 1 (or true) to give a 1 (or true) result.

The bitwise logic operators apply AND, OR, XOR, NOT operations on a bit by bit basis for the word operands. Like many other C and C++ operators they have equivalent forms that combine the operation with assignment so the general and operator is used like so (AND in this case):

Result = a & b;

But expressions of the form:

Result = Result & b;

Can be expressed using the operate-and-assign equivalent:

Result &= b;

Now back to mask operations. We create a mask that is a value that has only the bits we are interested in set to 1. When used with a bitwise AND operation with the value being masked the result is that all bits in the mask that are 0 will be 0 in the result and all bits that are 1 in the mask will have the value of the equivalent bit in the value being masked.

Thus if we use a mask of 0000 1111, then performing a bitwise AND with the value 1010 1010 will result in 0000 1010:

0000 1111 &
1010 1010
=
0000 1010

Using a mask of 0011 1100 on the value 0101 0101 yields the result 0001 0100:

0011 1100 &
0101 0101
=
0001 0100

Note: I am using binary above and elsewhere as it is easier to see what is going on. However C++ does not allow representing literal numeric values as binary, so we tend to use hexadecimal (or octal) literal values instead such as 0x0f rather than 0000 1111. This is also why I show binary values in groups of 4 bits, each group of 4 bits translates into a single hexadecimal digit.

In our case we need to test each bit in turn so our mask or masks should have only 1 bit set, so a mask of 0000 0001 when bitwise ANDed with the character value will give us 0000 0001 or 0000 0000 depending on whether the least significant bit is 1 or 0. If is 1 then we can add one to our count of 1 bits.

So what of the other bits in the character? Well we could create a mask for each bit: 0000 0001, 0000 0010 0000 0100 etc. or we could create the initial mask 0000 0001 and then shift it left using the left shift operator << (yes I know this is the C++ stream insertion operator, however C++ usurped the original shift left, shift right meanings of the << and >> operators to be the stream insertion and extraction). << and >> have shift-and-assign equivalents <<= and >>=.

Shifting the mask left one bit position each time will create a mask for each bit in the character in turn, thus:

0000 0001 << 1 gives 0000 0010
0000 0010 << 1 gives 0000 0100
0000 0100 << 1 gives 0000 1000
...
0100 0000 << 1 gives 1000 0000
1000 0000 << 1 gives 0000 0000 (1-bit shifted out of word yielding 0)

This leaves us with masked results of 0 or 1, 0 or 2, 0 or 4 etc. as each bit in the character is tested. So we would need something like the following to maintain the count and shift the mask left within the loop:

if ( character_value & mask )
{
++bit_count;
}

Assuming mask is the same type as character_value (i.e. char) then the loop should terminate when the mask value shifts beyond the most significant bit yielding a zero result.

The mask value would be initialised to 1. The if-statement condition makes use of the C and C++ definition of true as being any non-zero value.

We can turn this scheme around and always use a mask value of 1 but shift the bits of the character value right 1 bit position each time. In this case we loose the least significant bit and the next significant bit becomes the least significant bit. In effect we shift each bit in the character into the least significant bit position.

1001 0110 >> 1 gives 0100 1011
0100 1011 >> 1 gives 0010 0101
0010 0101 >> 1 gives 0001 0010
...
0000 0010 >> 1 gives 0000 0001
0000 0001 >> 1 gives 0000 0000 (last 1 bit shifted out giving 0)

We then just test the least significant bit for 0 or 1. As it is always the least significant bit we are testing the result of the operation at the word (char) level is also 0 or 1. We can therefore directly add this result to the count, thus:

character_value >>= 1;

Again the mask value would be initialised to 1, however this time it is constant. In which case a better name should be considered maybe:

character_value >>= 1;

Where LSB means least significant bit, and could be declared like so:

This version is quite neat but it does destroy the original value of character_value which may be a bad thing.

In this case the loop can quit as soon as there are no more 1 bits to count, so we can combine the above with the loop logic:

for ( char v(character_value); v != 0; v >>= 1 )
{
}

The loop also takes a copy of the original character value to work on to get around the problem of destroying the original value of the character. The count value should be initialised to 0 and LSB_Mask is constant and initialised to 1 as before.

Each time around the loop the value is tested to see if there are more 1 bits to count. If there are not then v will be 0. After each iteration v is updated by shifting it right one place, which is done as the 3rd expression in the for-statement.

Note that you can use the LSB_Mask with a bitwise AND operation to test the bit_count value to see if it is odd or even. Odd numbers when expressed in binary _always_ have a 1 value for the least significant bit.

Hope this helps.

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials