Чтобы отбросить последнюю цифру в двоичной записи числа нужно

Для начала представим себе, что данные в компьютерах хранятся в ячейках-«битах», каждое из которых может принимать 10 разных значений. В таком случае очень легко хранить положительные целые числа: каждое число по цифрам записывается в ячейки памяти. Реальный процессор может выполнять арифметические с такими числами, но есть проблема: чем больше цифр в числах, которые он сможет складывать за одну операцию (такт), тем сложнее его проектировать, тем больше тепла он выделяет и энергии потребляет. Поэтому необходимо выбрать некоторое фиксированную «стандартную» длину чисел так, чтобы с одной стороны для большей части основных задач числа туда помещались, с другой стороны были наиболее короткими. Например, можно выбрать длину в 10 цифр для «обычных» чисел и длину 20 для «длинных» (операций с длинными целыми числами за один такт процессора будет выполняться меньше). Кстати, нам потребуется хранить ещё и знак числа. Как лучше всего это сделать — вопрос очень хороший.

В реальности используется несколько подходов к хранению знака числа, вернее даже к хранению просто целых чисел. Самый «популярный» в данный момент называется «дополнение до двойки» (two’s complement), что для нашего воображаемого десятичного процессора превращается в «дополнение до десятки». Основная идея подхода состоит в следующем. Так как наши числа ограничены 10-ю цифрами, то если в результате арифметической операции возникнет перенос через разряд в 11-ю цифру, то он будет потерян. В таких случаях говорят, что вычисления производятся по модулю $10^$. Пусть у нас есть два числа: отрицательное $x$ и положительное $y$, и нам нужно вычислить $x+y$. Заметим, что по замечанию выше $x+yequiv (10^+x) + y$ (ведь добавление лишнего $10^$ ничего не меняет, у нас нет «места», чтобы хранить эту цифру). Но число $(10^+x)$ уже заведомо положительное.

Итак, ровно в этом состоит идея: для хранения отрицательного числа $x$ используется положительное число $(10^+x)$. Неотрицательные числа от 0000000000 до 4999999999 хранятся как есть. А числа от 5000000000 до 9999999999 отдаются отрицательным числам, причём $-1$ превращается в $10^-1 = 9999999999$, $-2$ превращается в $10^-2 = 9999999998$, и так далее, $-5000000000$ превращается в. в $-5000000000$. Заметим, что отрицательных чисел «поместилось» на одно больше, чем положительных.

Вот примеры: сложим $8,512$ и $-3,628$. $10^-3628 = 9,999,996,372.$ Далее $8,512 + (-3,628) equiv 8,512 + 9,999,996,372 = 10,000,004,884 equiv 4,884.$
Сложим $-6,460$ и $-9,290$. $(-6,460) + (-9,290) equiv (10^-6,460) + (10^-9,290) = 9,999,993,540 + 9,999,990,710 = $ $= 19,999,984,250 equiv 9,999,984,250 equiv 9,999,984,250 — 10^ = (-15,750).$

В чём выгода такого подхода? Во-первых, используются все возможные значения (если знак хранить в первой цифре, то будут «потеряны» 80% чисел). Во-вторых, с таким подходом отрицательные числа ничем не отличаются от положительных и не требуется усложнения схем для организации арифметических операций с ними. По модулю $10^$ отлично работают все арифметические операции, поэтому работать будут и вычитание, и умножение.

Разбор задачи на системы счисления . Подсчет единиц в двоичной записи числа

В реальных чипах используется двоичная система счисления, но в остальном всё устроенно именно так. Один бит — это двоичная цифра. И существуют числа разной длины — в 8, 16, 32 и 64 двоичных цифры. Это зависит от реальных чипов.

Битовое представление целых чисел и битовые операции

Итак, переменные типа int хранятся в двоичной системе счисления в виде последовательности двоичных цифр — бит. Биты нумеруются от 0, биты будем записывать справа налево (то есть бит с номером 0 будет записан самым правым, а самый старший бит — самым левым).

a = 0 # 0b0 a = 1 # 0b1 a = 2 # 0b10 a = 10 # 0b1010 a = 255 # 0b11111111

Например, если a = 10 , то в битовой записи a биты с номерами 1 и 3 равны 1, а остальные биты равны 0.

В программах на языке Питон числа в двоичной системе счисления можно записывать в виде последовательностей из 0 и 1, предваряя их префиксом 0b . Например, допустимо присваивание a = 0b101 .

Для двух переменных одинакового скалярного типа определены битовые операции:
b # 0b100 == 4 d = a | b # 0b111 == 7 e = a ^ b # 0b11 == 3 f = ~ a # 0b1. 11111010 == -6

Битовое отрицание числа (величина f в последнем примере) — это число, полученное из исходного заменой всех нулей на единицы и наоборот.

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

Есть еще две операции, работающие с битами: это битовые сдвиги. Их два: сдвиг влево и вправо. Оператор a >> n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например:

a = 43 # 0b101011 b = a >> 1 # 0b10101 == 21 c = a >> 2 # 0b1010 == 10 d = a >> 3 # 0b101 == 5 e = a >> 5 # 0b1 == 1

Понятно, что для положительных чисел битовый сдвиг числа вправо на n равносилен целочисленному делению на 2 n . Для отрицательных чисел в языке Питон операции битового сдвига неприменимы.

Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2 n и осуществляется при помощи оператора
a = 5 # 0b101 b = a

Если необходимо применить битовую операцию к переменной и результат сохранить в ней же, то можно использовать стандартные конструкции

n = k

Заменить последнюю единицу в двоичной записи числа на ноль

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

  • математика
  • битовые-операции
  • системы-счисления

Отслеживать
546 3 3 серебряных знака 18 18 бронзовых знаков
задан 2 дек 2013 в 10:13
25.9k 1 1 золотой знак 38 38 серебряных знаков 70 70 бронзовых знаков

без цикла не знаю, с циклом так можно, например: var a=6,i=0; while (a>>i<

2 дек 2013 в 10:43

С циклом и я знаю. =) В состоянии найти единичку в строке. Но задача именно без. В частном случае, когда число начинается только с единиц, а заканчивается только нулями, оно решается ($a

Двоичная система счисления

В этом разделе всюду речь идет о двоичной записи чисел.

Главное: Двоичная запись числа N означает представление этого числа в виде суммы степеней двойки. Места, на которых стоит 1, показывают, какие степени двойки нужно брать. Номер места отсчитывается справа налево и начиная с 0.

Примеры.
1) 25 = 16+8+1 = 2 4 + 2 3 + 2 0 . Поэтому 25 = 110012 .
2) 66 = 64 + 2 = 2 6 + 2 1 . Поэтому 66 = 10000102 .

Как переводить числа из десятичной системы в двоичную можно посмотреть, например, здесь. Хорошая книга лежит здесь. Непонятно — пишите.
Другие свойства следуют из этого свойства. Вот несколько примеров.

1. Четные числа оканчиваются на 0, нечетные – на 1.

2. Число 2 k в двоичной системе счисления записывается единицей и k нулями. Например, 32 = 2 5 в двоичной системе счисления записывается так: 100000

3. Число N делится на 2 k число N оканчивается на k нулей 4. Число 2 k – 1 в двоичной системе счисления записывается k единицами. Например, 31 = 2 5 – 1 в двоичной системе счисления записывается так: 11111 5. Двоичная запись числа N содержит ровно k цифр тогда и только тогда, когда Число N принадлежит интервалу 2 k-1 ≤ N ≤ 2 k — 1

Действительно, пусть, например, k=5. Наименьшее число, которое записывается 5-ю цифрами – это число 10000 2 = 2 4 = 16 10 . А наибольшее число, которое записывается 5-ю цифрами – это число 11111 2 = 2 4 + 2 3 + 2 2 + 2 1 + 2 0 = 16 10 +8 10 +4 10 +2 10 +1 10 = 31 10 = 32 – 1 = 2 5 – 1.

Еще один пример. Для числа 67 имеем: 64 = 2 6 ≤ 67 ≤ 2 7 — 1 = 127. Двоичная запись числа 67 содержит 7 цифр: 6410 = 10000112 = 2 6 + 2 1 + 2 0

PascalABC через целочисленные операции

var n, r, z, k: Integer; begin for n := 4 to 99 do begin z := n; k := 0; while z > 0 do begin k := k + z mod 2; z := z div 2; end; if k mod 2 = 0 then begin z := n * 2; k := 0; while z > 7 do begin k := k + 1; z := z div 2; end; r := n * 2 — z * round(power(2, k)) + 5 * round(power(2, k)); end else begin z := n * 4 + 3; k := 0; while z > 3 do begin k := k + 1; z := z div 2; end; r := n * 4 + 3 — z * round(power(2, k)) + 2 * round(power(2, k)); end; if r > 68 then begin Writeln(n); break; end; end; end.
#include #include using namespace std; string bin(int n) < string s = «»; while (n >0) < s = to_string(n % 2) + s; n /= 2; >if (s == «») s = «0»; return s; > int to_int(string s, int r) < int n = 0, z = 1; for (int i = s.length() — 1; i >= 0; i—) < n += ((int)s[i] — 48) * z; z *= r; >return n; > int count(string s, char c) < int n = 0; for (int i = 0; i < s.length(); i++) if (s[i] == c) n++; return n; >int main() < for (int n = 4; n < 100; n++) < string s = bin(n); if (count(s, ‘1’) % 2 == 0) < s += «0»; s = «101» + s.substr(3, s.length() — 3); >else s = «10» + s.substr(2, s.length() — 2) + «11»; int r = to_int(s, 2); if (r > 68) < cout > >

Задание №16 (системы счисления) в ЕГЭ 2016 по информатике
презентация к уроку по информатике и икт (11 класс) на тему

Презентация содержит теоретический материал, а также разбор решения некоторых заданий №16 ЕГЭ 2016 по информатике. Может быть полезна учащимся, учителям при подготовке к сдаче ЕГЭ.

ВложениеРазмер
ФайлПрезентация «Задание №16 (системы счисления) в ЕГЭ по информатике, 2016»202.08 КБ

Предварительный просмотр:

Подписи к слайдам:

Демо версии 2014, 2015, 2016

Что нужно знать : • принципы кодирования чисел в позиционных системах счисления ; • правила перевода из 10-ной в любую другую с.с . и соотношение между 2-ной, 8-ной и 16-ной с.с . ; • чтобы перевести число 12345 N , из системы счисления с основанием N в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду: 4 3 2 1 0 ← разряды 1 2 3 4 5 N = 1•N 4 + 2•N 3 + 3•N 2 + 4•N 1 + 5•N 0 • последняя цифра записи числа в системе счисления с основанием N – это остаток от деления этого числа на N • две последние цифры – это остаток от деления на N 2 , и т.д . • двоичная арифметика (сложение, вычитание, умножение) Этого было достаточно для решения задач до 2015 года!

В двоичном представлении числа инвертировать последнюю цифру. — Pascal

Завтра зачёт, а осталось сделать одну задачку. Вроде и не сложная, но я в программировании не силён. Если кто сможет помогите пожалуйста! Вот задачка: В двоичном представлении числа инвертировать последнюю цифру. (в задании рассматривается тип word) Замечание. При работе нельзя использовать массивы для хранения цифр двоичного представления чисел. Все действия необходимо выполнить, используя либо арифметические операции “+” или “-“ либо побитовые операции “shl”, “shr”, “and”, “or” или “xor” языка Pascal.

Листинг программы
if odd(n) // Если n — нечётное then dec(n) // n:=n-1 else inc(n) // n:=n+1

Объяснение кода листинга программы

Вот что происходит в этом коде:

  1. Проверка условия: является ли n нечётным числом.
  2. Если условие истинно (n — нечётное), то выполняется операция decrement (уменьшение на 1).
  3. Если условие ложно (n — чётное), то выполняется операция increment (увеличение на 1).
  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д

Разбор 6 задания ЕГЭ 2020 по информатике из демоверсии

6 задание. ЕГЭ-2020. Информатика. Демонстрационный вариант.

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа еще два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы ее цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

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

Разбор задания

Проанализировав алгоритм, легко догадаться, что если число нечетное, то в конец его двоичной записи добавляются цифры 1 и 0, а если четное — цифры 0 и 0.

Рассмотрим числа, большие 97, и найдем минимальное число, которое является результатом работы алгоритма.

Для этого, отбрасываем два последних разряда (две цифры) в двоичной записи числа. Далее складываем оставшиеся цифры и проверяем какое это число (четное или нечетное). Проверяем отброшенные ранее две последние цифры.

9810 = 11000 102 — не может являться результатом работы алгоритма (число четное 1 + 1 + 0 + 0 + 0 = 2, но последние две цифры не 00).

9910 = 11000 112 — не может являться результатом работы алгоритма (число четное 1 + 1 + 0 + 0 + 0 = 2, но последние две цифры не 00).

10010 = 11001 002 — не может являться результатом работы алгоритма (число нечетное 1 + 1 + 0 + 0 + 1 = 3, но последние две цифры не 10).

10110 = 11001 012 — не может являться результатом работы алгоритма (число нечетное 1 + 1 + 0 + 0 + 1 = 3, но последние две цифры не 10).

10210 = 11001 102 — является результатом работы алгоритма (число нечетное 1 + 1 + 0 + 0 + 1 = 3, последние две цифры 10).

ОТВЕТ: 102

Оцените статью
TutShema
Добавить комментарий