The binary operations problems are probably the ones, that can easily make a student to quit with programming tasks. They are somehow too abstract and the fun they bring is really doubtful. Anyway, in contests for programming so far, I have always avoided these problems, knowing that if I score quite good on the other ones I will probably be still amongst the top 10% of the participants. Thus, I have always neglected them, as being “too serious” and so. However, today I have decided to take a look at this problem, just for the sport.
The case is to convert some numbers to binary numbers and to count their Zeroes and Ones. Seems quite interesting actually, and it should not be that difficult. And the great point was, that I was able to get 100% of the tests correct in about 30 minutes!
So, how does it work?
1. We read the numbers and we count for each number how many binary digits it has, by counting how many times we can divide it by 2, before we reach 0 as a result:
|
1 2 3 4 5 6 7 8 9 10 11 |
for (long x = 0; x < N; x++) { myLong[x] = long.Parse(Console.ReadLine()); myLonger[x] = myLong[x]; counter = 0; while (myLonger[x] != 0) { myLonger[x] = myLonger[x] / 2; counter++; } } |
2. Then we simply have to take a look at the number and its last digit (represented as a binary). If the last digit is “1” and we use the “AND” binary operator with 1, it will return TRUE. Using this, we may write the following:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
secondCounter = 0; for (int i = 0; i < counter; i++) { if ((B==1) && ((myLong[x] & 1) == 1)) { secondCounter++; } if ((B == 0) && ((myLong[x] & 1) == 0)) { secondCounter++; } myLong[x] = myLong[x] >> 1; } Results[x] = secondCounter; |
As you see in the example, we have two cases – the first one is when we should count the occurences of the ZERO and the second one when we should count the occurences of the ONE. These cases are determined by the value “B”, which is given as input.
3. Finally, we should simply write the array(Results[x]), which we have on the console:
|
1 2 3 4 |
for (int i = 0; i < N; i++) { Console.WriteLine("{0}",Results[i]); } |
And we have a solution, giving 100%. Quite fast & fascinating. I was expecting a lot of problems and headaches, but – Nope, it was really as easy as that. Here comes the whole solution, enjoy it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Program { static void Main() { long B = long.Parse(Console.ReadLine()); long N = long.Parse(Console.ReadLine()); long[] myLong = new long[N]; long[] myLonger = new long[N]; long[] Results = new long[N]; long counter = 0; long secondCounter = 0; for (long x = 0; x < N; x++) { myLong[x] = long.Parse(Console.ReadLine()); myLonger[x] = myLong[x]; counter = 0; while (myLonger[x] != 0) { myLonger[x] = myLonger[x] / 2; counter++; } secondCounter = 0; for (int i = 0; i < counter; i++) { if ((B == 1) && ((myLong[x] & 1) == 1)) { secondCounter++; } if ((B == 0) && ((myLong[x] & 1) == 0)) { secondCounter++; } myLong[x] = myLong[x] >> 1; } Results[x] = secondCounter; } for (int i = 0; i < N; i++) { Console.WriteLine("{0}", Results[i]); } } } |