Обсуждение:Битовые операции

Untitled

Данная статья тематически связана с другими, и обсуждается в комплексе на странице Обсуждение проекта:Математика/Булева логика.

Рецензия 23-24 июня 2007 г.

Прошу знатоков computer science, булевой логики и дискретной математики помочь разобраться, что же это такое получилось. Incnis Mrsi 22:27, 23 июня 2007 (UTC)

Проблемы при написании статьи возникли следующие:

Охват

Похоже что я замахнулся на слишком многое: рассмотреть понятие как математическое (в основном из алгебры логики, но местами приходилось вспоминать про логические связки), как имеющее отношение к схемотехнике (логические элементы) и программированию (собственно эти самые операции). В результате рассмотрение прыгает с одного на другое. Incnis Mrsi 22:28, 23 июня 2007 (UTC)

Перенос чужих статей

У нас существовали две независимых статьи «XOR» и «сложение по модулю 2», контент которых я попытался перетащить, но не уверен что не забыл чего-то важного. Теперь там стоят редиры — может я бы и не грохал старые статьи, но их было 2 а сливать их именно в отдельную статью про XOR у меня не было никакого желания. Incnis Mrsi 22:27, 23 июня 2007 (UTC)

Термины

Я считаю что очень хорошо понимаю то, что пишу. Но не везде я уверен в корректности терминов, особенно когда всякие булевы алгебры начинают путаться с регистрами из программирования.

Ну к тому же статья местами стилистически безобразна, но критика стиля меня интересует в последнюю очередь. Incnis Mrsi 22:27, 23 июня 2007 (UTC)

Замечания от MarLex

Насколько я понимаю, битовыми операциями принято называть то, что в статье названо "Операции над битовыми векторами". По крайней мере, в программировании (например, упомянутые операторы С являются именно побитовыми). То, что перечисляется - это булевые операции, булевые функции, логические операции. Мне кажется, неправильно смешивать это в одной статье.

Имеет смысл сделать две статьи (это заодно решит проблему охвата).

1 - булевые функции, в которой находится первая часть данной статьи. Там будет речь именно об операциях с 0 и 1 (а не с векторами). Там же можно будет упомянуть про КНФ, ДНФ, про схемы из функциональных элементах, про некоторые полные классы функций.

2 - про побитовые операции. Это сделать на основе второй части данной статьи. Поподробнее описать, что же такое "побитовое И", "побитовое всё остальное", сюда же - регистровые сдвиги. Ко всему - примеры и обозначения из различных языков программирования (точно из C, может, из ассемблера).

Абсолютно согласен Sasha1024 12:31, 23 августа 2009 (UTC)

Это главное. Замечания по мелочи:

• Довольно странно написан раздел про "перечисление битовых операций". А именно, вызывает недоумение подраздел "Операции от многих аргументов". Впрочем, это по стилю, а стиль, я так понимаю, пока не обсуждается.
• Раздел "применение" какой-то нескладный. Понятно, о чём идёт речь, но... Идея о том, что роль битовых операций особенно велика в адаптере EGA - это как-то наивно. Компьютер только с битами и работает - это же не менее важно, чем графический ускоритель.

MarLex 23:59, 23 июня 2007 (UTC)

Операции над битовые векторами есть операции в булевой алгебре, мне не кажется правильным пилить по этому признаку, наоборот надо бы связь усилить. Раздел о применении, понятно, недоделан (статья-то сырая). Что касается EGA, то операции над битовыми векторами действительно были остроумно применены одновременно как средство ускорения вывода данных (для умных программ — я сам писал как-то низкоуровневый интерфейс к 16цветному режиму, правда не чистый EGA а 800x600) и заодно для экономии адресного пространства. Компьютер да, перемалывает биты конечно, но далеко не все операции над битовыми структурами сводятся к операциям в булевой алгебре (т.е. к побитным) или к сдвигам. Нужна инфа именно о применении булевых операций, а о сдвигах IMHO можно упомянуть вскользь (как это и сделано) и отправить их «на выселки», ибо тема тянет на отдельную статью. Incnis Mrsi 08:00, 24 июня 2007 (UTC)

Замечания от Kv75

Очень спорная статья (в плане построения). С одной стороны, очень хорошо иметь вот такую общую обзорную статью про все эти взаимосвязанные явления. С другой, не вполне понятно, где остановиться и на чём акцентировать внимание. Есть логические операции, есть операции над множествами, есть над битами. И хотя по своей глубинной сути это всё одно и то же, обозначения и названия разные. В общем, тут надо серьёзно думать над структурой статьи. Ещё маленький вопрос: а циклические сдвиги не заслуживают упоминания в разделе «операции над битовыми векторами»? Kv75 07:18, 24 июня 2007 (UTC)

Операции над битовыми векторами и в булевых алгебрах суть одно и то же. Проблемы исчисления высказываний я предпочёл бы обойти стороной (связки это отдельная тема и к битикам они не сводятся), но непонятно куда пихать разъяснения по поводу XOR, почему он так называется и вообще. До циклических сдвигов я не добрался потому, что мне было более интересно описывать операции над бесконечным битовым вектором, куда они не лезут (SHR и SAR там впрочем тоже не различаются, но для конечного случая оговорить различие было необходимо). Но в принципе циклические сдвиги конечно нужны. Incnis Mrsi 08:00, 24 июня 2007 (UTC)

Как по мне, «исключающее или» — это неудачный перевод с английского «exclusive or». Я бы перевёл это как «исключительное или». Т.е. исключительно в случае «или» (когда оба аргумента разные) результат равен единице. — Andrey 08:28, 24 июня 2007 (UTC)

Не считаю перевод (если таковой вообще имел место) неудачным, предложенный вариант во-первых является ориссом, а во-вторых привёл бы к недоумению про рассмотрении XOR от трёх и более аргументов (если оно «исключительное», то почему от (1,1,1) равно 1?). Прилагательное «исключающее» не столь категорично. Incnis Mrsi 10:01, 24 июня 2007 (UTC)

«Исключающее или» — это вполне стандартный термин, принятый во всех известных мне русских работах. Тут никаких проблем. Kv75 10:17, 24 июня 2007 (UTC)

Вот только не понимаю, зачем так кипятиться. Во-первых я не сказал, что нужно провести замену. У меня не один год образования и работы в области информатики, чтобы не знать, что «Исключающее или» — общепринятый термин. Только мне до сих пор так и не понятно, что же всё таки эта операция исключает? Если это не был перевод, откуда взялось тогда ещё сложение по модулю 2? Или кто-то решил два понятия ввести? Во-вторых про ориссы можете рассуждать в любом другом месте, я вообще в данном случае никогда не использую русский вариант. Если бы я написал статью «исключительное или», могли бы это и ориссом назвать. А в-третьих не мне вам объяснять, что операции XOR от трёх аргументов в принципе не существует. Вместо этого есть (a XOR b ) XOR c. Глубже надо смотреть. А то может мне расскажете, что есть XOR и от 50-ти аргументов? В любом случае объяснение "случай одновременной истинности аргументов «исключается»" не является адекватным. И объяснение «Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента.» можно и на более простое заменить: «Результат равен 1 только в том случае, если оба аргументы различны». Или что-то в этом духе. И кроме того, в статье кроме моего высказывания выше в слух и так много недочётов, о которых уже было упомянуто. — Andrey 14:31, 24 июня 2007 (UTC)

Попрошу обосновать высказывание операции XOR от трёх аргументов в принципе не существует — в математике является обычной практикой рассматривать ассоциативные бинарные операции как операции от произвольного положительного кол-ва аргументов, а если она ещё и обладает нейтральным элементом (а XOR вообще структуру группы вводит), то и хоть от нуля :) Во-вторых, фразу про ориссы можете рассуждать в любом другом месте считаю неспровоцированным проявлением агрессии, не способствующему конструктивной дискуссии. Ответ в том же духе но с большей конструктивностью: статьи ступайте писать, любезный! Incnis Mrsi 18:22, 24 июня 2007 (UTC)

Объясняю. Любая логическая операция определяется максимум для двух аргументов, хотя некоторые можно обобщать для нескольких аргументов. Естественно можно определить некоторую функцию, которая будет принимать три и более аргументов, а на выходе выдавать результат. Но в целесообразности такой функции я не вижу смысла, так как для её вычисления всё равно используется операция XOR для двух аргументов, разумеется. Если Вы увидели агрессию в моём высказывании, то я прошу прощения за её проявление. Однако Вы наверняка не попробовали в Гугле ввести логическое "исключительное или"? Результатов будет несравненно меньше, чем для исключающего, но тем не менее такой вариант тоже существует, он не мной придуман. Поэтому ориссом называть альтернативный вариант Вы поторопились, тем более, что на мой взгляд, другой вариант перевода (даже если он не является традиционным) не совсем правомерно называть ориссом, хотя я может быть не до конца понимаю значение этого модного слова. А что касается написания статей, то Вы об этом не переживайте, я уже не одну статью написал. — Andrey 21:26, 24 июня 2007 (UTC)

Кстати, ещё один момент перекликается с замечанием MarLex. В том же C есть битовые операции, а есть логические. И это разные вещи (& — битовая, а && — логическая). Поскольку в статье всё это несколько смешано, надо бы прояснить этот момент. Kv75 10:17, 24 июня 2007 (UTC)

Да, я уже над этим думал, но пока не знаю как это сделать изящно. Т.н. логические операции как раз ближе к связкам из ИВ, т.к. применяются как правило из-под if и т.п. конструкций. Для статьи это IMHO не основная тема. Incnis Mrsi 10:26, 24 июня 2007 (UTC)

Может, всё-таки более изящно разделить на две статьи? Давайте разберёмся в простой вещи: в каком источнике булевые операции называются битовыми? Просто есть ли такой? Если нет, то однозначно надо разделять. Если есть, то, возможно, в этом источнике мы сможем найти подсказку - как лучше всё структурировать. MarLex 16:58, 24 июня 2007 (UTC)

Пожалуйста, поясните свою точку зрения в свете последних подвижек. Если «слить логические операции с булевыми, а операции над векторами выделить», то я категорически против, см. talk:Логическая операция. Incnis Mrsi 18:33, 24 июня 2007 (UTC)

Я не хочу ничего никуда сливать. Вопрос простой: в каком источники булевые операции называются битовыми? Моё мнение, что битовые операции = операции над битовыми векторами. В таком смысле этот термин упоминается в языках программирования. В дискретной математике, насколько я помню, операции всегда называют булевыми, а не битовыми. Поэтому в статье идёт смешивание понятий. А значит, нужно не сливать, а разделять. Я это уже предлагала выше. Хацкер ниже предлагает то же. MarLex 21:18, 24 июня 2007 (UTC)

А, при первом ответе я пропустил мимо «множества». Вот этого ┌@% только не надо тут IMCO, ибо too controversal. Пускай убираются в теорию множеств или ещё куда подальше. Только битовые векторы, никакого Боже упаси Цермело и Кантора! Incnis Mrsi 08:21, 24 июня 2007 (UTC)

Хорошо, пусть убираются. :) Kv75 10:17, 24 июня 2007 (UTC)

Конечно, пусть. Но вообще-то довольно интересная мысль: написать популярную статью как раз про одноименные операторы И/ИЛИ/НЕ - с точки зрения логики, битов и множеств. MarLex 17:01, 24 июня 2007 (UTC)

А засунуть такую статью в алгебра логики не получится? IMHO надо посмотреть у англомэнов и прочих французов, может уже сделали что-то такое. Incnis Mrsi 18:22, 24 июня 2007 (UTC)

Замечания от Хацкера

Присоединяюсь к сомнениям предыдущих экспертов отностельно логической целостности статьи и предлагаю разделить её на Битовые операции и Булева функция, тем более что последнее до сих пор отсутствует в Википедии. В битовых операциях нужно ограничится описанием стандартных операций (AND, OR, XOR, сдвиги, и.т.д) и их использованием в программировании, схемотехнике и т.д. Описать все технические аспекты и детали реализации. В статье же Булева функция нужно рассмотреть ситуацию во всей общности, привести все стандартные теоретические сведения, включая функиональную полноту, критерий Поста, методы проверки фунциональной полноты, примеры полных сиситем функций (алгебру логики, алгебру Жегалкина, ...). Ну и понятно, как пример практического приминения сослатся на Битовые операции. Хацкер 19:13, 24 июня 2007 (UTC)

Не возражаю против выделения глубокой теории (нормальные формы, полные системы функций… ) в отдельную статью. У меня лишь вызывает недоумение предложение поделить статью по критерию области применения операций: над одним либо многими битами. Incnis Mrsi 20:50, 24 июня 2007 (UTC)

Нет, я не предлагал разделять статьи по количеству битов (в битовые операции например могут войти циклические здвиги — они определены для любой длинны). Критерий разделения, который я предлагаю — это: в битовые операции — более техническую информацию для программистов и схемотехников, и соотв. стандартные операции, которые используются на практике, а в булевы функции — общую теорию. Это будет хорошо соответствовать названиям. Хацкер 21:47, 24 июня 2007 (UTC)

У нас есть булева формула, только без interwiki и вообще её чистить надо т.к. там идёт обычная для дилетантов путаница между булевой алгеброй и исчислением высказываний. Может переименовать и привести её в достойный вид? Incnis Mrsi 06:31, 25 июня 2007 (UTC)

Кстати статья логика высказываний IMHO тоже является нездоровой пидерсией: описывает объект едва ли существующий, и является ненужным звеном. Возможно, её надо бы поделить между исчислением высказываний и булевой функцией (на которую будет стоять перенаправление с булева формула). Incnis Mrsi

Всем спасибо!

P.S. Всем большое спасибо за активный отклик. Incnis Mrsi 18:22, 24 июня 2007 (UTC)

Логическая vs. Побитовая логическая операция

В приведенном примере:

Следует различать логические операции и логические побитовые операции. Например, применение логического «И» к 2 и 1, то есть к двум «истинам», дает «истину», но результат побитового «И» от 2 и 1 равен нулю.

есть очень тонкий момент — совсем не объяснено, почему оба значения 2 и 1 соответствуют «истине» (и вообще как логическим значениям ставятся в соответствие числовые, и наоборот). Это надо как-то разяснить, а возможно также перенести этот пример, как слишком "ошарашивающий" неискушённого читателя, из шапки во внутрь статьи.

На самом деле это справедливо только в некоторых языках программирования, которые неявно преобразуют числовые типы к булевым. Даже в тех, где есть такое неявное преобразование, наверняка компилятор выдаст предупреждение. Поэтому снести это куда-то вниз и правильно объяснить состояние дел. --Kuzmaka 11:01, 15 января 2010 (UTC)

Уточнить нужно, но коротко и прямо там. Это причина многих заблуждений из-за исторически нечеткой терминалогии - поэтому различие нужно пояснить сразу. S.J. 11:07, 15 января 2010 (UTC)

Другие побитовые логические операции

Какие еще Вы пояснения хотите, что это булевы функции ? Названия у этих ваших "других" имеются ? Булевы операции это синоним побитовых логических операций. Слово функции действительно смущает, это математики так пишут, но суть от этого не меняется. Можно делать редирект Булевы операции - Булевы функции. А уж булевы опреации это и есть побитовые логические операции (другие, точнее 16 бинарных). S.J. 12:42, 18 января 2010 (UTC)

Вверху статьи не случайно помещена надпись Не следует путать c булевой функцией. Прочтите определение булевой функции (отображение {0,1}ⁿ → {0,1}). Сравните с тем, что такое побитовая логическая операция в математическом смысле (отображение N → N, или отображение {0,1}ⁿ → {0,1}ⁿ). --Kuzmaka 13:22, 18 января 2010 (UTC)

Давайте тогда это тонкое различие опишем в статье, а то слов не путать мало. S.J. 14:19, 18 января 2010 (UTC)

Да, надо бы конечно. Что-то подобное есть в разделе «Обобщение операций на булеву алгебру», но очень невнятно. --Kuzmaka 14:44, 18 января 2010 (UTC)

Различие принципиальное. Другое дело, что в статье Булева функция врядли целесообразно упоминать о примерах применения, взятых из языков программирования. А отдельное схемотехническое описание призрачных «битовых операций» может быть сочтено другими участниками ОРИССом и предложено к удалению. Зачем самому себе готовить почву для конфликта?!? --OZH 11:41, 19 января 2010 (UTC)

Соображения не ясны. В статье Булева функция достаточно лишь иметь раздел связь с программированием, где ее и показать связь с битовыми операциями. Если же говорить о схемотехнических описаниях - они уместны в статье Битовая операция (теория алгоритмов), т.к. именно эта теория оглядывается на время их выполнения, и наоборот, в схемотехнике реализуется, то что проходит ценз качества исходя из этой теории. Именно поэтому и затеяно разделение, которое просто необходимо: уточняет смысл, и разделяет россыпь статей к одной или другой, а не мешает все в кучу. S.J. 14:53, 19 января 2010 (UTC)

Пока не очень ясен предмет статьи Битовая операция (теория алгоритмов). Вот написали бы в личном пространстве (как я и предлагал уже, но Вы проигнорировали), предложили бы, и тогда можно было бы что-то затевать. А теперь можно всё сильно запутать. --OZH 18:37, 19 января 2010 (UTC)

Вам термин ясен ? S.J. 20:30, 19 января 2010 (UTC)

Мне тоже непонятно, на каких основаниях перенесена информация отсюда туда. --Kuzmaka 22:19, 19 января 2010 (UTC)

Перенесены там разделы Связь с другими науками и Практические применения. Если статья Битовая операция (программирование) получает четкий и ясный контекст - программирование (а за это есть все АИ), то связи с мат. логикой и цифровой техникой имеет смысл писать только с точки зрения Битовая операция (теория алгоритмов), т.к. мат. логика это исторический базис для теории алгоритмов, а цифровая техника - это воплощение теории алгоритмов. Так же и для применения реализация ВСЕХ комбинаций битовых операций в смысле теории алгоритмов, и уже только затем на основе реализованной технике предоставление для программирования части необходимых функций - отсюда и плаванье терминологии с отличиями. Такая структура позволяет (и в принципе уже играет эту роль) исторически разделить понятия, показав их непротиворечивую связь. И совершенно не логично, обратное, когда из Битовая операция (программирование) приходится описывать более широкие предпосылки. S.J. 23:38, 19 января 2010 (UTC)

«Связи с мат. логикой и цифровой техникой имеет смысл писать только с точки зрения Битовая операция (теория алгоритмов)» и дальше по тексту — ничем не подтвержденное сочинение. --Kuzmaka 08:39, 20 января 2010 (UTC)

Замечание о языках низкого уровня

В статье сказано:

«Ряд источников по языкам низкого уровня называет побитовые логические операции просто логическими [1][2]»

Читаем указанные источники (курсив мой):

(1) «Логические операции представлены командами NOT (инверсия), AND (конъюнкция), OR (дизъюнкция), XOR (исключающее ИЛИ) и коман­дой TEST». «Все логические операции являются поразрядными, т.е. выполняются независимо для всех бит операндов».

(2) «Турбо Ассемблер поддерживает полный набор инструкций для выполнения логических операций». «Логическая инструкция выполняет поразрядные операции над битами исходных операндов».

Можно ли в этом случае делать вывод, что эти источники называют «побитовые логические операции просто логическими»? Из приведенных цитат видно, что речь идет о реализации логических операций (операций из алгебры логики) командами или инструкциями в конкретном языке программирования, и что с помощью этих команд выполняются поразрядные (= побитовые) логические операции. --Kuzmaka 12:11, 21 января 2010 (UTC)

Разумеется. «Логические операции» есть поразрядные, утверждают источники по ассемблеру. Логические — определяемый термин, «поразрядные» и прочее — определение. В общем-то, неудивительно. Какие ещё «логические операции» могут быть в языке низкого уровня, кроме дрюченья битов? Там, где нет if, do, while и for — IMHO только такие. P.S. приведённые мною источники получены от vlsergey (обс. · вклад) в ходе частной беседы по поводу, как же надо всё-таки называть битовые операции. Incnis Mrsi 20:59, 21 января 2010 (UTC)