Побитови операции- проблем с намиране на 0 в битовете


0

Опитвам се да реша задача от изпит по C# част  1 - Search in Bits.

http://bgcoder.com/Contests/Practice/DownloadResource/872

Имам затруднения във намирането на битовете, които са 0. Като стартирам кода по долу, 

със стойности за S =0 , N=1; numbers[0]=1073741312; би трябвало counter-a да се

инкрементира 2 пъти и да приеме стойност 2, а вместо това показва 6. Не мога да открия 

къде греша, затова моля за помощ.

П.С В долното решение разглеждам само случая, когато за S сме задали стойност 0.

using System; class Bitwise { static void Main() { int numbers2; int counter = 0; int zero = 0; int result = 0; int number1; int number2; int number3; int number4; int bit1 = 1; int bit2 = 1; int bit3 = 1; int bit4 = 1; int result1; int result2; int result3; int result4; int mask1; int mask2; int mask3; int mask4; int S = int.Parse(Console.ReadLine()); int N = int.Parse(Console.ReadLine()); int[] numbers = new int[N]; if ((S > 15 || S < 0) || (N > 100 || N < 1)) { return; } else { for (int i = 0; i < N; i++) { numbers[i] = int.Parse(Console.ReadLine()); if (numbers[i] > 1073741823 || numbers[i] < 0) { return; } else { continue; } } foreach(int number in numbers) { if (S == 0) { for (int i = 0; i < 30; i++) { mask1 = bit1 << i; mask2 = bit2 << (i + 1); mask3 = bit3 << (i + 2); mask4 = bit4 << (i + 3); number1 = mask1 & number; number2 = mask2 & number; number3 = mask3 & number; number4 = mask4 & number; result1 = number1 >> i; result2 = number2 >> i + 1; result3 = number3 >> i + 2; result4 = number4 >> i + 3; if (result1 == 0 && result2 == 0 && result3 == 0 && result4 == 0) { counter++; } } Console.WriteLine(counter); } } } } }




Отговори



1

Проблема ти е, че проверяваш едновременно четири позиции, а увеличаваш брояча на цикъла с едно. Ако смениш 48-и ред така, ще ти върне резултат 2:

for (int i = 0; i < 30; i += 4) {

Не знам защо си форматираш кода в c#, все едно е JS, но определено не изглежда добре :)


от wnvko (3123 точки)


1

Условието на задачата ти е да намериш колко пъти поредица от 4 бита се среща в битовете на друго число.

За 32 бита разглеждайки 4 бита наведнъж при всяко завъртане, for цикълът тръбва да е до (i < 29), така при последното завъртане разглеждаш битове (28, 29, 30, 31), които са последните 4. В задачата ти е дадено да търсиш в само в първите 30 бита, тъй че цикълът трябва да е до (i < 27).

Ако for цикълът инкрементира с 4.

for(int i = 0; i < 27;  i+=4)

Ще разглеждаш битовете на групички по 4, което не ти върши работа.
(00111111111111111111111000000000 = 1073741312)

  1. 0011 1111 1111 1111 1111 1110 0000 0000
  2. 0011 1111 1111 1111 1111 1110 0000 0000
  3. 0011 1111 1111 1111 1111 1110 0000 0000

За задачата ти трябва да инкрементираш с едно, за да разглеждаш всяка поредица от 4 бита и точно това става в примерът, където се търсят 4 поредни нули и резултатът е 6.

  1. 00111111111111111111111000000000
  2. 00111111111111111111111000000000
  3. 00111111111111111111111000000000
  4. 00111111111111111111111000000000
  5. 00111111111111111111111000000000
  6. 00111111111111111111111000000000

Също така не ти трябват 4 маски с които намираш по един бит, можеш с една маска да намериш и четирите.

Mask: 00000000000000000000000000001111 = 15


от Pariador (60 точки)