Как да разбереме побитовите операции?

antonio_rtodorov 74 Точки

Как да разбереме побитовите операции?

Здравейте,

от опеделено време насам се ровя в интернет пространството за теми, които касаят побитовите операции. Наистина попаднах на доста интересни теми, които показват всеки един оператор какво действие извършва, тяхното прилагане в компютрите и т.н.

Предполагам, че всеки човек знае смисъла от десетичните уравненията (20 - 5 = 15; 20 + 5 = 25; 20 / 5 = 4; 20 * 5 = 100; -5 + 20 = 15 и т.н.), защото прави аналогия с дадени предмети ( като 20 ябълки минус 5 ябълки е равно на 15 ябълки) и знае какво е значението за прилагането на такъв тип математически действия. Ако използвам същите числа в бинарен вариант с операторите за бинарно изчисление (0001 0100 (20) & 0000 0101 (5) = 0000 0100 (4); 0001 0100 (20) | 0000 0101 (5) = 0001 0101 (21); 0001 0100 (20) ^ 0000 0101 (5) = 0001 0001 (17); i т.н. с ' ~ ' оператор) идва и моят проблем, с каква цел го правя, какъв е смисъла от прилагането на тези операции и подобни изчисления, какво е значението на получените числа след действията или може ли да си направиме някаква аналогия в ежедневието си за да ги разбереме по - добре?

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

Поздрави,

Тагове:

25/08/2015 15:08:10 Programming Basics

RoYaL Trainer 6849 Точки

Ту партс, дет се вика, поне това ми идва на прима виста - ако имаш нужда от огромен перформънс. Дето се вика да направиш елементарна аритметика побитово вместо с оператор за събиране/изваждане е хиляди пъти по-бързо.

Другото е когато става въпрос за системно програмиране, където побитовите репрезентации отговарят на някакъв стейт на машината. Какъвто де факто е най-елементарният пример, че нулев бит означава загасена крушка, а пък единица - светната такава. Което де факто защо го правиш с побитови операции, а не с някаква обектна абстракция отгоре - пак заради перформънс и ограниченията на съответното устройство.

TL;DR нямат приложение в ежедневното програмиране на средностатистическия програмист.

25/08/2015 16:23:52 25/08/2015 16:29:14

antonio_rtodorov 74 Точки

Да, именно точно това, което казваш е абсолютно правилно и го разбирам. Идеята ми е следната както знам, че с 5 + 5 = 10 и разбирам процеса защо всъщност използвам 5 и 5 с оператора '+' за да получа 10 и предполагам всеки човек го разбира, целта ми е със същото разбиране да постигна при побитовите операции.

Ти примерно как успя да ги разбереш, как да използваш двойчната система, с какво ти помага и т.н.?

Желанието ми е в това, че не искам да назубря побитовите операции и да ги смятам, защото така се смятат, а искам да ги разбера каква е тяхната функционалност. Според мене най - трудно е да правиш нещо, което не разбираш. В случая знам как да работя с операторите на побитовите операции, но не мога да разбера логиката, като правя нещо, но и аз не знам какво.

Поздрави,

25/08/2015 17:32:53

RoYaL Trainer 6849 Точки

Ако толкова държиш да разбереш приложеието им, намери такъв проект :)

По между другото има доста интересни топици по въпроса из интернет, например: http://programmers.stackexchange.com/questions/177685/what-kind-of-specific-projects-can-i-do-to-master-bitwise-operations-in-c-als и http://stackoverflow.com/questions/2096916/real-world-use-cases-of-bitwise-operators

25/08/2015 18:22:09

byclops 126 Точки

Според мен, освен ако не си особен вид математически гений, ще ти е трудно да си представиш интуитивно побитовите операции по начина, по който възприемаш аритметичните операции.

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

Например:

1010 & 0001 = 0000

Тук проверяваме дали нулевия бит на числото 10 (в двоичен вид 1010) е 0 или 1. Ако е нула резултата също ще е нула, в противен случай - едно.

Можем да проверим например едновременно за нулевия и третия бит:

1010 & 1001 = 1000

Тук резултата ще е:

0000, ако и двата са 0

0001, ако само нулевия бит е 1

1000, ако само третия бит е 1

1001, ако и дваата са 1

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

На процесорно (или може би по-ниско?) ниво почти всички аритметични, логически, сравнителни (а сигурно и други типове) операции се свеждат до побитови опверации. Това е един вид естествения начин да се обработват двоични числа. Тук вече човешката интуиция съвсем не важи - това са си алгоритми, които са математически изведени.

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

25/08/2015 19:41:44

antonio_rtodorov 74 Точки

Да, наистина доста интелигентно си го представил и ти благодаря за отделеното време. Може би просто ми е трудно да разбера нещо, което реално нямам ясна представа как мога да го приложа. Това е причината да отворя и тази тема, защот пресмятам битове намирам дадени стойности, които както обясни имат своето място, което същност аз търся. Най - вече по мое наблюдение не е и толкова лесно да ги разбереш, защото то е ясно, че 5+5=10, но 5 & 5 != 10 и точно това ме побърква, защото съм се научил да броя, но как да се науча и да "побитувам" ако мога да се изразя :D

25/08/2015 20:48:41

RoYaL Trainer 6849 Точки

Научил си се да броиш, но не си се научил да умножаваш трицифрени числа на ум, нали?

Ако не си крайно извратен, логично, едва ли ще "побитуваш" на ум, точно както е умножаваш трицифрени на ум.

По същият начин, по който пресмяташ трицифрени, така подхождай и тук - раздели си решението на малки стъпки.

1. Имаш десетично число, например 4.

2. Превръщаш го в двоична система. 4 делено на 2 има мода/остатък(%) 0, остават 2. Останалото 2 делено на 2 има мода 0, остава 1. Останалото едно делено на 2 има мода 1 и не остава нищо. Обръщаме го обратно и числото в двоична е 100. С много нули отпред според зависимост колко битово ни е цялочисленото, ако е int (Int32) -> още 29 нули. (00...00100)

3. Трябва на това число да смениш първия бит (от дясно на ляво, като се започва от нулев бит) на обратния бит на какъвто е в момента.

4. Как се променя бит? Имаме три оператора - OR, AND, XOR (|, &, ^). При OR, ако имаме поне един положителен бит, резултатът ще е положителен бит. При AND трябва и двата бита да са положителни (1) за да имам резултат с положителен бит. При XOR ако са различни, ще върне единица. Ако са еднакви ще върне 0. Т.е. ако битат в момента на тази позиция е 1 и го XOR-неш с 1 - ще върне 0. Ако битът е 0 и го XOR-неш с 1 ще върне 1. Т.е. трябва ти XOR, и то с единица, за да се промени бита. XOR с 0 ще остави битът същият. Което е супер, защото това означава че можем всички други битове да ги XOR-нем с нула и само този с единица, за да променим само него и запазим всички други.

5. Как да XOR-нем с единица само този бит? Ами това означава, че ни трябва число, което има на всички други позиции нулеви битове и само на 1ва позиция единичен бит (00...010). Принципно това число е 2, но нека работим по-абстрактно

6. Взимаме число, което на нулева позиция завършва на 1 и всички други битове са му нула (00...0001). Това число е 1

00 00 00 01

7. Местим всичките му битове наляво, толкова позиции, колкото е позицията, на която искаме да променим бита. Т.е. позиция 1. Всички битчета се местт една позиция наляво, а най-отляво ако се появяват нови битове това са 0 (ще ползваме bold за преместен бит и ~~зачеркване~~ за новодошъл бит). Операцията е едно (1) изместено на ляво (<<) един (1) път = 1 << 1

00 00 00 10

8. Нека поставим побитовата репрезентация на четири (4) на един ред и тази на новополученото ни число (1 << 1) на един ред под него

00 00 01 00 (4)

00 00 00 10 (1 << 1)

9. Нека извършим XOR между тези две числа. Това означава че бит по бит един под друг както са, ще се извърши XOR. Започваме от ней-десния бит (нулевия) наляво. Отгоре е 0 и отдолу е 0, XOR (0 ^ 0) = 0. Първият бит отгоре е 0, отдолу е 1, XOR (0 ^ 1) = 1. Вторият бит отгоре е 1, отдолу е 0, XOR (1 ^ 0) = 0. Третият бит, както и всички останали, отдолу са 0 и отгорре са нула, XOR (0 ^ 0) = 0. Какъв стана резултатът (болднатите числа от дясно на ляво)

00 00 01 10 демек (00...00110) = 6

10. Т.е. когато на четворката промениш битът на 1ва позиция на обратния на какъвто е бил се получава 6ца. Console.WriteLine(4 ^ (1 << 1)); Аналогично ако извършиш този XOR върху 6ца (новополученото число) ще върнеш тази 1ца на 0 и отново ще се получи 4ка.

Прилича ли ти на това как би сметнал 268 * 191? В смисъл такъв ако извадиш тетрадката и раздробиш това на малки стъпки пак ще имаш едни 10 основни :)

25/08/2015 22:29:10