[C#] Домашно Operators and Expressions - 14 задача


32

 

Задача:
* Write a program that exchanges bits {p, p+1, …, p+k-1) with bits {q, q+1, …, q+k-1} of given 32-bit unsigned integer.
 
Измислих някакво решение, но ще ми е интересно и другите как постъпват към тази задача :)
 
Изпълнявам следните стъпки
 
Питам колко бита ще сменяме: 1,2,3... ?
Питам за позицията на първата група битове за смяна - например 4та
Питам за позицията на втората група за смяна - например 21ва
 
Съответно ако е избрано да се сменят общо поредица от 3 бита ще се сменят:
4,5,6ти с 21,22,23ти бит.
 
Създавам маска със 1ци за съответния брой битове и съответната позиция, които искаме да сменим.
За близката група/4ти,5ти,6ти бит/ битове: 000000...1110000 
За далечната група /21ви,22ри,23ти/ битове: 00000..111000000000000000000000
 
Копирам сегашните стойности на съответните битове в числото в отделни маски с & AND оператор след което измествам битовете съответно в най-дясна позиция.
 
запаметени битове близка група = (Числото & маска–близка-група ) >> изместваме до най-дясна позиция
запаметени битове далечна група = (Числото & маска–далечна-група ) >> изместваме до най-дясна позиция
 
По този начин имаме запаметени съответните битове в най-дясно.
 
След това занулявам /000/ стойностите на съответните битове /4ти,5ти,6ти бит и на 21ви,22ри,23ти бит/ като предварително съм създал маски 
зануляваща маска за близка група - 11111111111111111111111110001111
зануляваща маска за далечна група - 11111111000111111111111111111111
 
След това използвам оператора & AND, за зануля съответните битове и да запазя старите стойности на другите битове.
(Числото & зануляваща маска за близката група)
(Числото & зануляваща маска за далечна група)
 
Измествам запаметените битове до съответната позиция:
 
запаметени битове близка група << до позицията на далечната група
запаметени битове далечна група << до позицията на близката група
 
След което ползвам оператора | OR, за да копирам битовете на съответните позиции:
 
Числото = Числото | (маска-запаметени-битове-близка-група-преместени-на-далечна-позиция)
Числото = Числото | (маска-запаметени-битове-далечна-група-преместени-на-близка-позиция)
 
Please enter how much bits you would like to exchange: 3
Please enter which is the first NEAR bit you'd like to exchange: 4
Please enter which is the first MORE FAR bit you'd like to exchange: 21
The value of the NEAR bit is: 101
The value of the MORE FAR bit is: 101
The mask for the NEAR bit is: 1110000
The mask for the MORE FAR bit is: 111000000000000000000000
Value to be Changed BEFORE transformation:     1010101100100011110011011101
Value to be Changed AFTER set to NEAR BIT:     1010101100100011110010001101
Value to be Changed AFTER se MORE FAR BIT:     1010000100100011110010001101
The Value of (~maskForMoreBit)           : 11111111000111111111111111111111
The Value of (~maskForNearBit)           : 11111111111111111111111110001111
Value to be Changed with ZERO-ED BIT:     1010000100100011110010001101
Value to be Changed with NEAR BIT   :     1010000100100011110011011101
Value to be Changed with FAR  BIT   :     1010101100100011110011011101
00:00:00.0030000
Press any key to continue . . . 
 
 
 
 
 
edit: заглавие на темата и таговете



Отговори



7

Предоставям 2 решения, първото с побитови операции, другото е по-елементарно.



  1. using System;
  2.  
  3. class Program
  4. {
  5.     static void Main(string[] args)
  6.     {
  7.  
  8.         Console.WriteLine(@"!!'p' shouldn't be greater than 'q', and 'k'+'q' shouldn't be greater than 32!!");
  9.         Console.WriteLine("First write the number, then p->q->k");
  10.         uint number;
  11.         byte q, k, p;
  12.         bool isNum = uint.TryParse(Console.ReadLine()out number);
  13.         bool isP = byte.TryParse(Console.ReadLine()out p);
  14.         bool isQ = byte.TryParse(Console.ReadLine()out q);
  15.         bool isK = byte.TryParse(Console.ReadLine()out k);
  16.         string str = Convert.ToString(number, 2).PadLeft(32'0');
  17.         Console.WriteLine("Before : {0}", str);
  18.         p = (byte)(p-1);
  19.         q=(byte)(q-1);
  20.  
  21.         if ((isNum && isP && isQ && isK) && (< q && (+ q) <= 32))
  22.         {
  23.             while (!=0)
  24.             {
  25.                 int mask = 1 << p, maskSecond = 1 << q;
  26.                 uint maskBit = (uint)(number & mask);
  27.                 uint maskBitS = (uint)(number & maskSecond);
  28.                 if ((maskBit >> p) == (maskBitS >> q)) { goto here; }
  29.                 if ((maskBit >> p) != (maskBitS >> q) && (maskBit >> p != 0))
  30.                 {
  31.                     int reverseMask = ~(1 << p);
  32.                     number = (uint)(number | maskSecond);
  33.                     number = (uint)(number & reverseMask);
  34.                    
  35.                 }
  36.                 else if ((maskBit >> p) != (maskBitS >> q) && (maskBitS >> q != 0))
  37.                 {
  38.                     int reverseMask = ~(1 << q);
  39.                     number = (uint)(number | mask);
  40.                     number = (uint)(number & reverseMask);
  41.                    
  42.                 }
  43.             here: ;
  44.                 p++;
  45.                 q++;
  46.                 k--;
  47.             }
  48.             Console.Write("After :  ");
  49.             Console.WriteLine(Convert.ToString(number, 2).PadLeft(32'0'));
  50.         }
  51.         else Console.WriteLine("Wrong Input");
  52.     }
  53.  
  54. }

Eми аз се направих на "недоразбрал" и имплементирах друго решение, което може да не работи в общият случай по-бързо от побитовите операции, но разликата няма да голяма, защото не заделям 8 байта за 2 маски, тоест времето ще е приблизително еднакво.

 

 

  1. using System;
  2.  
  3. class Program
  4. {
  5.     static void Main(string[] args)
  6.     {
  7.  
  8.        //int temp = int.MaxValue;
  9.         //uint uTemp = (uint)(temp*2)+1;
  10.         Console.WriteLine(@"!!'p' shouldn't be greater than 'q', and 'k'+'q' shouldn't be greater than 32!!");
  11.         Console.WriteLine("First write the number, then p->q->k");
  12.         uint number;
  13.         byte q, k, p;
  14.         bool isNum = uint.TryParse(Console.ReadLine()out number);
  15.         bool isP = byte.TryParse(Console.ReadLine()out p);
  16.         bool isQ = byte.TryParse(Console.ReadLine()out q);
  17.         bool isK = byte.TryParse(Console.ReadLine()out k);
  18.  
  19.         string str = Convert.ToString(number, 2).PadLeft(32'0');
  20.         char[] array = new char[str.Length];
  21.         Console.WriteLine("Before : {0}",str);
  22.  
  23.         if((isNum && isP && isQ && isK) && (p<&& (k+q)<=32)){
  24.         for (int i = 0; i < str.Length; i++)
  25.         {
  26.             array[i] = str[i];
  27.         }
  28.  
  29.         for (int i = 0; i < k; i++)
  30.         {
  31.             char t = array[str.Length-q];
  32.             array[str.Length - q] = array[str.Length - p];
  33.             array[str.Length - p] = t;
  34.             q++;
  35.             p++;
  36.         }
  37.         Console.Write("After :  ");
  38.         for (int i = 0; i < str.Length; i++)
  39.         {
  40.             Console.Write(array[i]);
  41.         }
  42.         Console.WriteLine();
  43.         }
  44.         else Console.WriteLine("Wrong Input");
  45.     }
  46.    
  47. }

от Prophian (1234 точки)


0
Колко ти е времето за изпълнение, и как го измерваш ? Защото в момента това което правя аз е след входа на данните, защото ги извличам с Console.ReadLine() слагам един timestamp накрая на изчисленията вадя DateTime.Now от предишния timestamp и резултата е 30мс Този метод съм почти сигурен, че не е правилен, но за сега не успявам да погледна как да го направя.

от vlad0 (6103 точки)

0
Щом ти връща резултат значи става, в програмирането няма правилен и неправилен метод, има просто различен подход към проблема, пробвай с 2 DateTime.Now, като разликата между двата ти е времето на работа на програмата.
Също виж тука, поне 5-6 варианта има : http://stackoverflow.com/questions/1285052/how-long-does-my-code-take-to-run
!!'p' shouldn't be greater than 'q', and 'k'+'q' shouldn't be greater than 32!! First write the number, then p->q->k 13215214 1 15 16 Before : 00000000110010011010010111101110 After : 00101001011110110000001100100110 00:00:00.0026894 Press any key to continue . . .

от Prophian (1234 точки)



3
Здравейте,
браво и на двамата !
побитовото решение е вярно, дори накрая на упражненията с последното останало момиче го изкоментирахме, за жалост имаше само още 1-2ма човека.
Решението със char масива също не е грешно, нали работи :).
Интересното тук беше да се опитате да го направите побитово, за да се упражните за изпита, там ще има побитови операции.
За char масива, има функция toCharArray(), може да се възползваш от нея и да си спестиш първия for.
Поздрави,
Борис Гуцев

от Boris (3959 точки)


0
Знаех си че има функция, но когато го писах и достъп до интернет нямаше, така че това беше първото нещо, което ми дойде на глава.
Мерси (:

от Prophian (1234 точки)

0
Не че е грешно така, просто казвам, че има и готова функция. Постъпил си правилно, не си успял да намериш функцията, направил си си я сам :) Принципно, като сложиш точка (.) и VS ти подсказва, може със стрелките нагоре и надолу да минавате през методите предоставени на готово и да ги преглеждате :)

от Boris (3959 точки)


3
След малко играчка, аз измъдрих ей това:
http://pastebin.com/tfU720CZ
Малко заобикалям използването на побитови оператори, но по-нататък ще си поиграя и конкретно с тях. Също така не съм правил проверка за вход.
Ще се радвам, на всякакви коментари и препоръки :)
Едит: За да не се обърка някой като гледа решението - числата в конзолата ми се изкарват отзад напред - това преспокойно може да се оправи, чрез обръщане на list - a с "numberInBin.Reverse();"
Поздрави
Теодор

от Teodor92 (13062 точки)


0
Само направи числото uint и после каствай там на другите места да не гърми.

от kirov (4821 точки)

0
Мда като ми остане време ще го метна всичко към uint.

от Teodor92 (13062 точки)



1
Здравей,
а пробвал ли си с други данни, в момента нямам много време и VS за да тествам, но ми се струва че това ще изгърми при някое "number" , но може и да греша.
Решението е оригинално, аз нямаше да се сетя да използвам лист :)
Ето доказателство за това, че едно нещо може да се реши по доста различни начини :)
За входни данни, първите теми се предполага, че ви се подават коректни данни. По нататък ще трябва да предвиждате ако потребителя е некоректен какво да правите :)
Поздрави
Борис Гуцев

от Boris (3959 точки)


0
Еми пробвах с 10-на числа и на никое не направи проблем, но винаги има възможност да съм пропуснал нещо :)

от Teodor92 (13062 точки)


7

Ето и моето незряло решение, използващо общо взето само побитови операции: 

http://pastebin.com/NfhRDynL.

Като гледам колегите, доста ми трябва, докато започна да измислям по- елегантни варианти.


от Z_Petrov (829 точки)


4

Ето моето побитово решение на задачата. :) Писал съм подробни коментари, за да се разбере какво правим.

http://pastebin.com/uxGMJgeF

Поздрави,

Стоян

 


от kirov (4821 точки)


5
Най-накрая едно решение на задачката и от мен :)
http://pastebin.com/uKpZscn6
Не е толкова професионално като решението с масивите, но работи добре.

от atodorova (1273 точки)


1
Ето и моето решение на задачата, наистина има различни начини на решение :)
http://pastebin.com/4Q0spZk1

от AsenVal (3487 точки)


1

Привет, ето го и моето решение: http://pastebin.com/frzA35Yc

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


от georgi.ivanov (3261 точки)


2
Ето моето сравнително просто решение:

http://pastebin.com/cgstCqNG