Копирование бита

@taras atavin · Регистрация: 24.11.2009

Author24 — интернет-сервис помощи студентам

Надо упростить и оптимизировать строку

C++

1	p=((p&0x80)>>8)\|(*p&0x80);

. Задача - скопировать (не переместить) старший бит байта в младший бит того же байта.

@Deviaphan · 26.06.2012, 07:14

Сообщение от taras atavin

и оптимизировать строку

Начнём с того, что твой код работает не правильно. В нём содержится целых ДВЕ ошибки.
1. (*p&0x80)>>8) всегда равно нулю (для байтов)
2. Для числа 0х1 копирование старшего бита должно "обнулить" число, но у тебя младший бит по прежнему останется единицей.

Так что ты для начала научись писать ПРАВИЛЬНО работающие функции, а потом уже думай над их оптимизацией.

@taras atavin · 26.06.2012, 08:01 **[ТС]**

Забыл, что с ноля. Старший то седьмой, а я пытался двинуть восьмой.

C++

1	p=((p&0x80)>>7)\|(*p&0x80);

.

Добавлено через 1 минуту
Но, что самое смешное, с такими ошибками работал код, зависимый от этого. Только мог глючить при удержании.

@Deviaphan · 26.06.2012, 08:14

Ошибку "номер 2" теперь исправляй. Сейчас у тебя не копирование старшего бита, а установка единицы. Если старший бит нулевой, но на младшем это не сказывается. Чини дальше.)

@taras atavin · 26.06.2012, 09:23 **[ТС]**

Было 0b1000 0000, *p&0x80=0b1000 0000, (*p&0x80)>>7=0b0000 0001, ((*p&0x80)>>7)|(*p&0x80)=0b1000 0001, стало 0b1000 0001, теперь было 0b0000 0001, *p&0x80=0b0000 0000, (*p&0x80)>>7=0b0000 0000, ((*p&0x80)>>7)|(*p&0x80)=0b0000 0000, стало 0b0000 0001. Ошибка теперь у тебя, там "побитовое И", оно учитывает оба операнда. И залипание/отлипание теперь работает без глюков, кнопки отлипают как при повторном нажатии их самих, так и при нажатии противоположных им. И две кнопки не залипают в принципе, как и задумано. Две залипают только при повторном нажатии их самих, так тоже задумано. На удержание реагируют только не залипающие. Так тоже задумано.

@Deviaphan · 26.06.2012, 09:38

Сообщение от taras atavin

Ошибка теперь у тебя

Сообщение от taras atavin

Задача - скопировать

Ты ведь знаешь, что такое копирование?
было 0х1
(0b00000001 & 0x80)>>7 = 0
0 | 1 = 1
Т.е. после "копирования" старшего бита в младший, значение младшего не поменялось, хотя должно стать нулём.
То, что реализовано у тебя, это ни разу не копирование. Если написать более явный код, то во как выглядит твой алгоритм:

C++

1
2
3

BYTE p = ...;
if( p & 0x80 )
   p |= 1; // или p += 1;

Как видишь, это совсем не то же самое, что КОПИРОВАНИЕ старшего бита, для которого код выглядит так

C++

BYTE p = ...;
if( p & 0x80 )
    p |= 1;
else
   p &= 0xFE; // обнуляю младший бит

@taras atavin · 26.06.2012, 09:50 **[ТС]**

Сообщение от Deviaphan

Ты ведь знаешь, что такое копирование?
было 0х1
(0b00000001 & 0x80)>>7 = 0
0 | 1 = 1

В старшем бите в этом примере был 0, он и скопирован.

Добавлено через 3 минуты

Сообщение от Deviaphan

0 | 1 = 1
Т.е. после "копирования" старшего бита в младший, значение младшего не поменялось, хотя должно стать нулём.

чего это вдруг? 0|0, а не 0|1 Смотри внимательно правый операнд оператора "побитовое ИЛИ". Там не исходное число, а снова операция, отбрасывающая все биты, кроме старшего. Коды такие: 0x00 - давно отпущена, или ни когда не нажималась, 0x01 - только что отпущена, 0x80 - только что нажата, 0x81 - давно нажата. То есть оба бита имеют самостоятельные значения: старший - флаг текущего состояния кнопки, младший - флаг предыдущего её состояния.

Добавлено через 6 минут

Сообщение от Deviaphan

p &= 0xFE; // обнуляю младший бит

Есть одна особенность: байт - только код, фактическая разрядность хранимой величины два бита, а не восемь, просто код предусматривает дополнение до байта нолями в середине.

@Deviaphan · 26.06.2012, 09:55

Сообщение от taras atavin

Смотри на внимательно правый операнд оператора "побитовое ИЛИ".

Я не про "ИЛИ", а про слово КОПИРОВАНИЕ говорю. Ты выполняешь логическое сложение, а не копирование. КОПИРОВАНИЕ это когда берёшь ноль и записываешь ноль. Т.е. результат равен оригиналу. Всё прочее НЕ копирование. Давай говорить не в терминах битов, а в терминах чисел.
Было a = 0, b = 1;
Выполняем КОПИРОВАНИЕ: b = a; Вопрос, чему равно b?

@taras atavin · 26.06.2012, 10:49 **[ТС]**

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

Добавлено через 5 минут
Будет ли быстрее такой код:

C++

struct T2Flags
{
 int Current:1;
 int Zero:6;
 int Old:1;
};
((T2Flags *)p)->Old=((T2Flags *)p)->Current;

?

Добавлено через 46 минут

Сообщение от Deviaphan

Давай говорить не в терминах битов, а в терминах чисел.

Давай

Сообщение от Deviaphan

Было a = 0, b = 1;
Выполняем КОПИРОВАНИЕ: b = a; Вопрос, чему равно b?

0.Было a = 1, b = 0;
Выполняем КОПИРОВАНИЕ: b = a; внимание вопрос: чему равно a. Если убрать "побитовое ИЛИ", то нолю, то есть вместо копирования получим перенос.

@Deviaphan · 26.06.2012, 15:51

Сообщение от taras atavin

Если убрать "побитовое ИЛИ

Банальная логика подсказывает, что после копирования источник значения (бит, из которого копируется) и приёмник (бит, в который копируют) становятся равны. Эквивалентность этих величин определяет термин "копирование". Т.к. этому "явлению" уже тысячи лет, предлагаю данный момент забыть и закрыть.

Сообщение от taras atavin

a = 1, b = 0;
Выполняем КОПИРОВАНИЕ: b = a;

а не изменится, т.к. она справа. Независимо от операции.) А b станет равно 1.

Сообщение от taras atavin

Будет ли быстрее такой код:

Нет, не будет. "Ручная" работа с битами будет эффективнее. В лучшем случае, компилятор сможет "написать" такой же код, как и при маскировании битов.

@taras atavin · 26.06.2012, 16:49 **[ТС]**

Сообщение от Deviaphan

Банальная логика подсказывает, что после копирования источник значения (бит, из которого копируется) и приёмник (бит, в который копируют) становятся равны. Эквивалентность этих величин определяет термин "копирование". Т.к. этому "явлению" уже тысячи лет,....

вот только ты этого не знаешь до сих пор и приходится объяснять.

@Deviaphan · 26.06.2012, 16:51

Сообщение от taras atavin

вот только ты этого не знаешь до сих пор и приходится объяснять.

@taras atavin · 26.06.2012, 16:55 **[ТС]**

Сообщение от Deviaphan

а не изменится, т.к. она справа. Независимо от операции.)

Ты забываешь, что это части одного и того же байта. c=a*2+b (c состоит из цифр a и b), и a=1, b=0, тогда c=2, с&0b10 = 0b10=2, (c&0b10)>>2=0b01=1, выполняем

C++

1	c=(c&0b10)>>2;

, получаем c=1, при a*2+b, стало a=0, а b =1. (c&0b10)>>2 - это новое b, но присваиваю то я не b, а c, а это сумма. Ну так я и пишу

C++

1	c=(c&0b10)>>2+(c&0b10);

, где (c&0b10) - это a.

@Deviaphan · 26.06.2012, 17:03

Сообщение от taras atavin

Ты забываешь, что это части одного и того же байта.

Я приводил пример с независимыми a и b. Почему с независимыми? Потому что бит 7 и бит 0 не зависят друг от друга.
Давай попроще, с двумя битами нарисую.
Число b01
Как выполнить КОПИРОВАНИЕ?
Берём значение бита один и копируем его в бит ноль. При этом бит ноль становится таким же, как и бит один. Потому что, после копирования приёмник и источник становятся равны. Т.е. после копирования число будет b00. Любая другая операция, после которой число будет другим копирование НЕ является.
Блин, мне уже не смешно. Пойду поем.

@taras atavin · 26.06.2012, 17:21 **[ТС]**

Сообщение от Deviaphan

Я приводил пример с независимыми a и b. Почему с независимыми? Потому что бит 7 и бит 0 не зависят друг от друга.
Давай попроще, с двумя битами нарисую.
Число b01
Как выполнить КОПИРОВАНИЕ?
Берём значение бита один и копируем его в бит ноль. При этом бит ноль становится таким же, как и бит один. Потому что, после копирования приёмник и источник становятся равны. Т.е. после копирования число будет b00. Любая другая операция, после которой число будет другим копирование НЕ является.
Блин, мне уже не смешно. Пойду поем.

Берём число 123 и копируем старшую цифру в младшукю. Получим 121. Цифры после копирования равны друг другу, но число целиком неизбежно изменится, так как выполнена операция над цифрами одного и того же числа, которые не были равны, но стали равны. Так вот, запомни: биты - не числа, а цифры. Всегда. А число - это минимум байт. Задача скопировать одну цифру байта в другую цифру того же байта. Если они не были равны до копирования, то он должен измениться. А если число из 123 стало 21, то во-первых оно тоже изменилось, а во-вторых это не копирование, а перенос. Если же цифры уже равны, то операция избыточна.

@Deviaphan · 26.06.2012, 17:42

Сообщение от taras atavin

Берём число 123 и копируем старшую цифру в младшукю. Получим 121.

Да!
А если 120, то получим 121. А если 023, то получит 020. Я об этом.

@taras atavin · 26.06.2012, 18:04 **[ТС]**

Но если из 123 выделить старшую цифру, то получается 100, если теперь её сдвинуть до младшей, то получаем 001. Если теперь всему числу присвоить 001, то оно станет 001. А надо 121. Поэтому надо ещё раз выделить все цифры, кроме младшей и сложить их со старшей, сдвинутой на место младшей. 001+120=121, что и требовалось получить. Это операции с цифрами, а присваивается целиком число.

Добавлено через 3 минуты
Вопрос: битовыми полями будет быстрее? Через них присваивается отдельная цифра.

Evg · 26.06.2012, 18:08

Сообщение от taras atavin

Вопрос: битовыми полями будет быстрее?

Нет, не быстрее - Расскажите про new и delete в C++

Не надо оптимизировать там, где компилятор и без тебя построит оптимальный код. Вместо того, чтобы оптимизировать что-то в надежде выиграть два такта, лучше оптимизировать структуру программы и ускорить её в разы

В конце-концов, если есть вопрос "а как быстрее", то напиши оба варианта и посмотри на ассемблерную выдачу

@taras atavin · 26.06.2012, 18:18 **[ТС]**

Речь не о том, где компилятор умеет строить оптимальный код, а о том, не проглядел ли я собственную пессимизацию и не сработала ли она, не смотря на усилия компилятора. Ведь не каждую же мою глупость он может предусмотреть. Ну так так надо дать ему тот вид, где глупостей меньше и где он точно сможет построить оптимальный код. Я вот гадаю, то ли действительно сделать ифом, что подразумевает переходы, но только одну логическую операцию в каждой ветви и того две, то ли выписать в одну строчку, но тогда их набирается 3 + ещё операция сдвига, то ли дать компилу семантику всего куска в виде единственной операции, но с битовыми полями вместо собственных представлений о способе исполнения. Что из этого будет быстрее? Операция то частая, должна выполняться десятками, если не сотнями тысяч в секунду и ладно бы сама по себе, так фиг там, в довесок к графике на миллион+ полигонов в двух окнах.

Evg · 26.06.2012, 18:19

В любом случае совет не оптимизировать спички является актуальным

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 07:14	2
	Сообщение от taras atavin и оптимизировать строку Начнём с того, что твой код работает не правильно. В нём содержится целых ДВЕ ошибки. 1. (*p&0x80)>>8) всегда равно нулю (для байтов) 2. Для числа 0х1 копирование старшего бита должно "обнулить" число, но у тебя младший бит по прежнему останется единицей. Так что ты для начала научись писать ПРАВИЛЬНО работающие функции, а потом уже думай над их оптимизацией. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 08:14	4
	Ошибку "номер 2" теперь исправляй. Сейчас у тебя не копирование старшего бита, а установка единицы. Если старший бит нулевой, но на младшем это не сказывается. Чини дальше.) 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 09:23 [ТС]	5
	Было 0b1000 0000, p&0x80=0b1000 0000, (p&0x80)>>7=0b0000 0001, ((p&0x80)>>7)\|(p&0x80)=0b1000 0001, стало 0b1000 0001, теперь было 0b0000 0001, p&0x80=0b0000 0000, (p&0x80)>>7=0b0000 0000, ((p&0x80)>>7)\|(p&0x80)=0b0000 0000, стало 0b0000 0001. Ошибка теперь у тебя, там "побитовое И", оно учитывает оба операнда. И залипание/отлипание теперь работает без глюков, кнопки отлипают как при повторном нажатии их самих, так и при нажатии противоположных им. И две кнопки не залипают в принципе, как и задумано. Две залипают только при повторном нажатии их самих, так тоже задумано. На удержание реагируют только не залипающие. Так тоже задумано. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 09:50 [ТС]	7
	Сообщение от Deviaphan Ты ведь знаешь, что такое копирование? было 0х1 (0b00000001 & 0x80)>>7 = 0 0 \| 1 = 1 В старшем бите в этом примере был 0, он и скопирован. Добавлено через 3 минуты Сообщение от Deviaphan 0 \| 1 = 1 Т.е. после "копирования" старшего бита в младший, значение младшего не поменялось, хотя должно стать нулём. чего это вдруг? 0\|0, а не 0\|1 Смотри внимательно правый операнд оператора "побитовое ИЛИ". Там не исходное число, а снова операция, отбрасывающая все биты, кроме старшего. Коды такие: 0x00 - давно отпущена, или ни когда не нажималась, 0x01 - только что отпущена, 0x80 - только что нажата, 0x81 - давно нажата. То есть оба бита имеют самостоятельные значения: старший - флаг текущего состояния кнопки, младший - флаг предыдущего её состояния. Добавлено через 6 минут Сообщение от Deviaphan p &= 0xFE; // обнуляю младший бит Есть одна особенность: байт - только код, фактическая разрядность хранимой величины два бита, а не восемь, просто код предусматривает дополнение до байта нолями в середине. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 09:55	8
	Сообщение от taras atavin Смотри на внимательно правый операнд оператора "побитовое ИЛИ". Я не про "ИЛИ", а про слово КОПИРОВАНИЕ говорю. Ты выполняешь логическое сложение, а не копирование. КОПИРОВАНИЕ это когда берёшь ноль и записываешь ноль. Т.е. результат равен оригиналу. Всё прочее НЕ копирование. Давай говорить не в терминах битов, а в терминах чисел. Было a = 0, b = 1; Выполняем КОПИРОВАНИЕ: b = a; Вопрос, чему равно b? 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 15:51	10
	Сообщение от taras atavin Если убрать "побитовое ИЛИ Банальная логика подсказывает, что после копирования источник значения (бит, из которого копируется) и приёмник (бит, в который копируют) становятся равны. Эквивалентность этих величин определяет термин "копирование". Т.к. этому "явлению" уже тысячи лет, предлагаю данный момент забыть и закрыть. Сообщение от taras atavin a = 1, b = 0; Выполняем КОПИРОВАНИЕ: b = a; а не изменится, т.к. она справа. Независимо от операции.) А b станет равно 1. Сообщение от taras atavin Будет ли быстрее такой код: Нет, не будет. "Ручная" работа с битами будет эффективнее. В лучшем случае, компилятор сможет "написать" такой же код, как и при маскировании битов. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 16:49 [ТС]	11
	Сообщение от Deviaphan Банальная логика подсказывает, что после копирования источник значения (бит, из которого копируется) и приёмник (бит, в который копируют) становятся равны. Эквивалентность этих величин определяет термин "копирование". Т.к. этому "явлению" уже тысячи лет,.... вот только ты этого не знаешь до сих пор и приходится объяснять. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 16:51	12
	Сообщение от taras atavin вот только ты этого не знаешь до сих пор и приходится объяснять. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 17:03	14
	Сообщение от taras atavin Ты забываешь, что это части одного и того же байта. Я приводил пример с независимыми a и b. Почему с независимыми? Потому что бит 7 и бит 0 не зависят друг от друга. Давай попроще, с двумя битами нарисую. Число b01 Как выполнить КОПИРОВАНИЕ? Берём значение бита один и копируем его в бит ноль. При этом бит ноль становится таким же, как и бит один. Потому что, после копирования приёмник и источник становятся равны. Т.е. после копирования число будет b00. Любая другая операция, после которой число будет другим копирование НЕ является. Блин, мне уже не смешно. Пойду поем. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 17:21 [ТС]	15
	Сообщение от Deviaphan Я приводил пример с независимыми a и b. Почему с независимыми? Потому что бит 7 и бит 0 не зависят друг от друга. Давай попроще, с двумя битами нарисую. Число b01 Как выполнить КОПИРОВАНИЕ? Берём значение бита один и копируем его в бит ноль. При этом бит ноль становится таким же, как и бит один. Потому что, после копирования приёмник и источник становятся равны. Т.е. после копирования число будет b00. Любая другая операция, после которой число будет другим копирование НЕ является. Блин, мне уже не смешно. Пойду поем. Берём число 123 и копируем старшую цифру в младшукю. Получим 121. Цифры после копирования равны друг другу, но число целиком неизбежно изменится, так как выполнена операция над цифрами одного и того же числа, которые не были равны, но стали равны. Так вот, запомни: биты - не числа, а цифры. Всегда. А число - это минимум байт. Задача скопировать одну цифру байта в другую цифру того же байта. Если они не были равны до копирования, то он должен измениться. А если число из 123 стало 21, то во-первых оно тоже изменилось, а во-вторых это не копирование, а перенос. Если же цифры уже равны, то операция избыточна. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	26.06.2012, 17:42	16
	Сообщение от taras atavin Берём число 123 и копируем старшую цифру в младшукю. Получим 121. Да! А если 120, то получим 121. А если 023, то получит 020. Я об этом. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 18:04 [ТС]	17
	Но если из 123 выделить старшую цифру, то получается 100, если теперь её сдвинуть до младшей, то получаем 001. Если теперь всему числу присвоить 001, то оно станет 001. А надо 121. Поэтому надо ещё раз выделить все цифры, кроме младшей и сложить их со старшей, сдвинутой на место младшей. 001+120=121, что и требовалось получить. Это операции с цифрами, а присваивается целиком число. Добавлено через 3 минуты Вопрос: битовыми полями будет быстрее? Через них присваивается отдельная цифра. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	26.06.2012, 18:08	18
	Сообщение от taras atavin Вопрос: битовыми полями будет быстрее? Нет, не быстрее - Расскажите про new и delete в C++ Не надо оптимизировать там, где компилятор и без тебя построит оптимальный код. Вместо того, чтобы оптимизировать что-то в надежде выиграть два такта, лучше оптимизировать структуру программы и ускорить её в разы В конце-концов, если есть вопрос "а как быстрее", то напиши оба варианта и посмотри на ассемблерную выдачу 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	26.06.2012, 18:18 [ТС]	19
	Речь не о том, где компилятор умеет строить оптимальный код, а о том, не проглядел ли я собственную пессимизацию и не сработала ли она, не смотря на усилия компилятора. Ведь не каждую же мою глупость он может предусмотреть. Ну так так надо дать ему тот вид, где глупостей меньше и где он точно сможет построить оптимальный код. Я вот гадаю, то ли действительно сделать ифом, что подразумевает переходы, но только одну логическую операцию в каждой ветви и того две, то ли выписать в одну строчку, но тогда их набирается 3 + ещё операция сдвига, то ли дать компилу семантику всего куска в виде единственной операции, но с битовыми полями вместо собственных представлений о способе исполнения. Что из этого будет быстрее? Операция то частая, должна выполняться десятками, если не сотнями тысяч в секунду и ладно бы сама по себе, так фиг там, в довесок к графике на миллион+ полигонов в двух окнах. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	26.06.2012, 18:19	20
	В любом случае совет не оптимизировать спички является актуальным 0