Разное

Умножение двоичных чисел: Сложение двоичных чисел онлайн

Содержание

Умножение двоичных чисел 8-ми разрядным МК.

РадиоКот >Статьи >

Умножение двоичных чисел 8-ми разрядным МК.

Здравствуйте, уважаемые!

Появление КотоРеда толкнуло меня на написание сего труда – написание алгоритмов и программ для математических операций умножения и деления двоичных чисел. Однажды столкнувшись с подобной проблемой, я решил просто помочь тем, на кого эти «действия», выложенные в интернете без подробного описания наводят благоговейный ужас. Итак: писал я на Ассемблере для PIC16, однако постараюсь донести саму суть и методику (одну из) для широкого понимания. На авторство решения я ни в коем случае не претендую, поэтому прошу не говорить про плагиат.

Умножение:

Для выполнения математических операций сложения и вычитания служит АЛУ – арифметико-логическое устройство, в число задач которого входит, помимо ненужных нам пока функций сложение с вычитанием. А так как перед нами стоит задача выполнять умножение, то остановимся подробнее на методике его выполнения. Умножение двоичных чисел производится также как и десятичных – в столбик. Пример показан на картинках ниже в десятичном и двоичном вариантах.

  

Если присмотреться внимательней, то можно увидеть, что множитель как бы сдвигается вправо и умножение каждый раз производится на самое правое его число (в примере двоичного умножения – нулевой бит регистра множителя). А так как в двоичной системе имеются только нули и единицы, то результатом умножения является либо множитель, либо нулевой регистр, следовательно пошаговое умножение можно заменить сложением с последующим сдвигом полученного числа!

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

  1. Так как количество суммирований равно числу бит множителя, занесем в регистр counter (произвольная переменная — счетчик проходов) число бит, в приведенном примере равное 8-ми.
  2. Сдвигаем множитель вправо через бит carry (признак переноса). Если в carry логическая 1, то переходим к п. 5.
  3. Суммируем средний байт (регистр) будущего ответа с младшим байтом (регистром) множимого, и если было переполнение (бит carry), то увеличиваем старший байт будущего ответа на 1. 
  4. Суммируем старший байт (регистр) будущего ответа со старшим байтом (регистром) множимого.
  5. Производим поочередный сдвиг вправо старшего регистра ответа, затем среднего и, наконец, младшего.
  6. Уменьшаем счетчик бит counter на 1 с проверкой, закончились ли проходы? Если нет, то возвращаемся к п. 2.

После всех проведенных операций умножение закончено. В графическом виде алгоритм приведен ниже:

                   Графический алгоритм подпрограммы умножения.

Возможные вопросы:  почему производим сдвиг ответа вправо? Да потому, что первое число, полученное в результате умножения нужно сдвинуть именно вправо относительно последующего значения. Если это значение равно нулевому регистру, то производится простой сдвиг ответа вправо (переход с п. 2 на п. 5). Это можно хорошо рассмотреть на картинке с примером двоичного умножения выше на шагах 1-2-3-4.

Пример кода, написанный на Ассемблере для PIC16:

       MOVLW   0xAA

       MOVWF   BARGB0    ; множитель

;———————————-

       MOVLW   0xAA

       MOVWF   AARGB0    ; младший байт множимого

       MOVLW   0x55

       MOVWF   AARGB1    ; старший байт множимого

;———————————-

       CLRF    TEMPB0         ; младший байт ответа

       CLRF    TEMPB1         ; средний байт ответа

       CLRF    TEMPB2         ; старший байт ответа

       CALL    SMUL1608L

_1_

   GOTO    _1_                ; зацикливание для окончания счета и                  

                             ; проверки правильности работы программы

 

SMUL1608L                  ; подпрограмма умножения

 

       MOVLW   0x08          ; число проходов

       MOVWF   COUNT

LOOPSM1608

       RRF     BARGB0,F      ; сдвиг вправо множителя

       BTFSS   STATUS,C    ; в младшем разряде единица?

  GOTO    LSM1608NA

        MOVFW   AARGB0     ; младший байт множимого

        ADDWF   TEMPB1,F   ; складываем с средним байтом ответа

        BTFSC   STATUS,C     ; и, если произошло переполнение

        INCF    TEMPB2,F       ; увеличим старший байт ответа на 1

        MOVFW   AARGB1     ; старший байт множимого

        ADDWF   TEMPB2,F   ; складываем со старшим байтом ответа

LSM1608NA

        RRF     TEMPB2,F         ; поочередный сдвиг регистров ответа

        RRF     TEMPB1,F         ; вправо

        RRF     TEMPB0,F

        DECFSZ  COUNT, F        ; уменьшим число проходов на 1

        GOTO    LOOPSM1608   ; с проверкой на окончание

        RETLW   0         ; проходы вышли – выход из подпрограммы.

 END

   При наращивании разрядности, например 16*16 бит, число проходов counter должно равняться 16, а в ответе нужно предусмотреть еще один регистр, который нужно будет сдвигать самым последним, т.к. в приведенном алгоритме ответ сдвинется на 16 бит (2 регистра). Для упрощения приведу пример сложения двухбайтного числа:

  1. Суммируем младший байт (регистр) 1-го слагаемого с младшим байтом (регистром) второго.
  2. Если произошел перенос, увеличим на 1 старший байт второго слагаемого.
  3. Суммируем старший байт (регистр) 1-го слагаемого со старшим байтом (регистром) второго.

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

Все вопросы в Форум.


Как вам эта статья?

Заработало ли это устройство у вас?

ЧЕТЫРЕ СПОСОБА УМНОЖЕНИЯ

МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

Кафедра «Компьютерные системы и технологии»

Б.Н. Ковригин

АЛГОРИТМЫ УМНОЖЕНИЯ

СОДЕРЖАНИЕ

ЧЕТЫРЕ СПОСОБА УМНОЖЕНИЯ ……………………………………………

3

1. Алгоритмы умножения с младших разрядов множителя…………… 3

а) Умножение с младших разрядов множителя и сдвигом множимого влево …………………………………………………….. 3

б) Умножение с младших разрядов множителя и сдвигом суммы частичных произведений вправо …………………………… 3

2. Алгоритмы умножения со старших разрядов множителя ………….. 4

а) Умножение со старших разрядов множителя и сдвигом

 

множимого вправо ……………………………………………………. 4

б) Умножение со старших разрядов множителя и сдвигом

 

суммы частичных произведений влево …………………………….. 5

УМНОЖЕНИЕ ЧИСЕЛ В СПЕЦИАЛЬНЫХ КОДАХ ……………………….

6

Умножение чисел в прямом коде ……………………………………….….. 6 Умножение чисел в дополнительном коде ………………………….…….. 6

1.Умножение чисел в дополнительном коде с коррекцией результата в случае отрицательного множителя ……………….…. 7

2.Умножение чисел в дополнительном коде с предварительным изменением знаков сомножителей в случае отрицательного множителя …………………………………………………………… 14

3.Умножение чисел в дополнительном коде путем последовательного преобразования множителя ………………….. 22

Умножение чисел в обратном коде ………………………………….……. 25

1.Умножение чисел в обратном коде с коррекцией результата в случае отрицательного множителя ……………………………… 25

2.Умножение чисел в обратном коде с предварительным изменением знаков сомножителей в случае отрицательного множителя …………………………………………………………… 34

3.Умножение чисел в обратном коде с последовательным преобразованием множителя в случае отрицательного множителя …………………………………………………………… 34

СПИСОК ЛИТЕРАТУРЫ………………………………………………………………………………..

40

2

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

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

1. Алгоритмы умножения с младших разрядов множителя

а) Умножение с младших разрядов множителя и сдвигом множимого влево

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

П=A×B = A × (bn-1 рn-1 + . . . + b1 р1 + b0 р0) = A рn-1 bn-1+ . . . + A р1 b1+ A р0 b0 (1)

Проиллюстрируем этот способ умножения (как и все последующие) в десятичной р=10 и двоичной р=2 системах счисления.

 

 

Пример 1

 

 

 

 

 

Пример 2

 

 

 

 

А

6

2

1

 

 

 

А

 

1

0

1

1

 

 

 

 

В

 

2

0

1

b

 

= 1

В

 

1

1

0

1

 

0

 

 

 

 

6

2

1

0

 

 

1

0

1

1

b0

 

 

0

0

0

 

b

= 0

 

0

0

0

0

 

A 2

1

 

 

 

1

 

 

 

b1

1 2

4

2

 

 

b

= 1

1

0

1

1

 

 

A 2

2

 

 

2

 

 

 

b2

П =

 

 

 

 

 

b

= 1

1 0

1

1

 

 

 

A 2

3

1 2

4 8 2 1

3

 

 

 

 

b3

 

 

 

 

 

 

 

П =

 

 

 

 

 

 

A 2

 

 

n

 

 

n

 

 

 

1 0 0

0

1

1

1

1

 

 

 

 

 

 

 

 

 

 

n

 

 

 

n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

б) Умножение с младших разрядов множителя и сдвигом суммы частичных произведений вправо

Этот способ умножения подробно описан в учебной литературе [1-4, 6, 8, 11, 12]. Данный алгоритм умножения в указанной литературе приводится для дробных двоичных чисел и задается следующим выражением:

Z = X×Y = ((…((0 + Xyn) 2-1 + Xyn-1) 2-1 + … + Xy2) 2-1 + Xy1) 2-1

Для натуральных чисел в р-ичной системе счисления данный алгоритм умножения можно представить выражением (2):

П = A×B = pn {((…((0 + А b0) p-1 + А b1) p-1 + … + А bn-2) p-1 + А bn-1) p-1} (2)

Проиллюстрируем этот способ умножения в десятичной р=10 и двоичной р=2 системах счисления.

 

 

 

Пример 3

 

 

 

 

 

 

Пример 4

 

 

 

 

 

 

А

6

2

1

 

 

 

 

А

1

0

1

1

 

 

 

 

 

 

В

2

0

1

 

 

 

 

В

1

1

0

1

 

 

 

 

 

 

 

 

6

2

1

 

 

 

 

b0 = 1

 

1 0 1 1

 

 

 

 

0+Аb

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

0

6

2

 

1

 

 

 

0

1

0

1

1

 

 

 

П1 2-1

 

 

0

0

0

 

 

 

 

b1 = 0

0 0 0 0

 

 

 

 

Аb1

 

 

 

0

6

2

 

1

 

 

 

 

0

1

0

1

1

 

 

 

П12-1+Аb1=П2

 

0

0

6

 

2 1

 

 

0

0

1

0

1

1

 

 

П2 2-1

 

 

1 2

4

2

 

 

 

 

b2 = 1

1 0 1 1

 

 

 

 

Аb2

 

 

1 2

4

8

 

2 1

 

 

 

1

1

0

1

1

1

 

 

П22-1+Аb2=П3

 

1

2

4

 

8 2 1

 

0

1

1

0

1

1

1

 

П3 2-1

 

 

 

 

 

n

 

 

 

n

b3 = 1

1 0 1 1

 

 

 

 

Аb3

 

 

 

 

 

 

 

 

 

 

 

 

1

0

0

0

1

1

1

1

 

П32-1+Аb3=П4

 

 

 

 

 

 

 

 

 

 

 

1

0

0

0

1

1

1

1

П 2-1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n

 

 

 

n

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

После выполнения n циклов умножения получаем П={П4 2-1} 24 = {1000,1111} 24 = 10001111.

Таким образом, результат умножения получается простым перенесением запятой вправо на n разрядов.

2. Алгоритмы умножения со старших разрядов множителя

а) Умножение со старших разрядов множителя и сдвигом множимого вправо

Этот способ умножения также подробно описан в учебной литературе [1-4, 6, 8, 11, 12]. Для дробных двоичных чисел он задается следующим выражением:

Z = X×Y =X 2-1 y1 + X 2-2 y2 + … + X 2-n+1 yn-1 + X 2-n yn

Для натуральных чисел в р-ичной системе счисления данный алгоритм умножения можно представить выражением (3):

П = А×В = pn {А p-1 bn-1 + А p-2 bn-2 + … + А p-n+1 b1 + А p-n b0}

(3)

 

Проиллюстрируем этот способ умножения в десятичной р=10 и двоичной

р=2 системах счисления.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример 5

 

 

 

 

 

Пример 6

 

 

 

 

 

А

6

2

1

 

 

 

 

А

1

0

1

1

 

 

 

 

 

В

2

0

1

 

 

 

 

В

1

1

0

1

 

 

 

 

А 2-1 b3

 

 

1

2

4

2

 

 

 

b3 = 1

0

1

0

1

1

 

 

 

 

0

0

0

0

0

 

 

b2 = 1

0

0

1

0

1

1

 

 

А 2-2 b2

 

0

0

0

6

2

1

 

b1 = 0

0

0

0

0

0

0

0

 

А 2-3 b1

 

 

1

2

4

8

2

1

 

b0 = 1

0

0

0

0

1

0

1

1 А 2-4 b0

 

 

 

 

n

 

 

n

 

 

 

 

1

0

0

0

1

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n

 

 

 

n

 

 

Результат умножения П = {1000,1111} 24 = 10001111.

б) Умножение со старших разрядов множителя и сдвигом суммы частичных произведений влево

Описание данного способа умножения можно найти в [1-4, 6, 8].

Для натуральных чисел в р-ичной системе счисления данный алгоритм умножения можно представить в следующей форме (4):

П = A×B = (…((0 + А b n-1) p+1 + А b n-2) p+1 + … + А b1) p+1 + А b0

(4)

Проиллюстрируем этот способ умножения в десятичной р=10 и двоичной р=2 системах счисления.

 

 

Пример 7

 

 

 

 

 

Пример 8

 

 

 

 

 

 

 

 

 

А

 

6

2

1

 

 

 

 

А

 

1

0

1

1

 

 

 

 

 

 

В

1

2

0

1

 

 

 

 

В

 

1

1

0

1

 

 

 

 

 

 

 

2

4

2

 

 

 

 

 

 

1

0

1

1

 

0+А b3=П1

1

2

4

2

0

 

 

 

 

 

1

0

1

1

0

 

П 2

 

 

 

 

 

0

0

0

 

 

 

 

 

 

1

0

1

1

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

А b2

 

 

 

1

2

4

2

0

 

 

 

 

1

0

0

0

0

1

 

П

2+Аb

1 2

4

2

0

0

 

1

0

0

0

0

1

0

 

1

2

2

 

 

П 2

 

 

 

 

 

6

2

1

 

 

 

 

 

 

0

0

0

0

 

2

 

 

П =

 

 

 

 

 

 

 

 

 

 

А b1

 

1 2 4 8 2 1

 

 

 

1

0

0

0

0

1

0

 

П

2+Аb

 

 

n

 

 

n

 

 

1 0

0

0

0

1

0

0

 

2

1

3

 

 

 

 

 

 

 

П 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

1

1

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

А b0

 

 

 

 

 

 

 

 

 

 

1 0

0

0

1

1

1

1

 

П = П32+Аb0

 

 

 

 

 

 

 

 

 

 

 

n

 

 

 

n

 

 

 

 

 

УМНОЖЕНИЕ ЧИСЕЛ В СПЕЦИАЛЬНЫХ КОДАХ

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

В = b020 + b12-1 + b2 2-2 + …+ bn2-n ,

где b0 − знаковый разряд,

b1 ÷ bn − цифровые разряды.

Умножение чисел в прямом коде

Операция выполняется в два этапа. Отдельно определяется знак произведения 3П сложением по модулю 2 знаковых разрядов сомножителей:

3П = 3А 3В .

Затем определяется цифровая часть произведения путем перемножения цифровых частей сомножителей с нулевыми знаковыми разрядами.

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

Умножение чисел в дополнительном коде

Можно отметить три специфических варианта умножения чисел, представленных в дополнительном коде:

умножение с коррекцией результата в случае отрицательного множителя,

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

умножение путем последовательного преобразования множителя.

Ещё раз подчеркнем, что в каждом из перечисленных вариантов может быть использован один из четырех рассмотренных способов умножения.

1. Умножение чисел в дополнительном коде с коррекцией результата в случае отрицательного множителя [1-3,5,6,8,9]

Обозначим сомножители через А и В, а их абсолютные величины — черезА и В . Если некоторый сомножитель, скажем В, положителен, то в его основных разрядах (без разряда знака) содержится величина В , если же он отрицателен, то в его основных разрядах содержится величина 1- В (дополнение от величины В до единицы).

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

Так как цифровые разряды в изображении множителя В представляют либо величину В (если В > 0), либо величину 1- В (если В < 0), то результат (псевдопроизведение) этого процесса умножения будет равен либо

А×В = А×В (если В ≥ 0)

либо

А× (1- В ) = А — А×В = А + А×В (если В < 0).

В первом случае получаем сразу готовое произведение, во втором случае (если В < 0) нужно выполнить один корректирующий шаг — вычитание из псевдопроизведения множимого А. При выполнении вычитания обычным образом учитываются алгебраические знаки псевдопроизведения и множимого.

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

а) Умножение с младших разрядов множителя и сдвигом множимого влево

Выражение (1), которое является аналитическим представлением данного способа умножения, для случая сомножителей, представляющих правильные дроби в 2-ичной системе счисления в дополнительном коде (для цифровой части множителя без учета возможной коррекции результата), трансформируется в выражение (5):

[П]д = [A]д × [B]д = 2-n {[A]д 2n-1 b1+ . . . +[A]д 21 bn-1+ [A]д 20 bn}

(5)

Проиллюстрируем этот способ умножения при различных сочетаниях знаков сомножителей.

Пример 9. [A]д = 1.0010 [B]д = 1.0101

 

 

 

 

 

1

0

0

1

0

Множимое [A]

 

 

 

 

 

.

0

1

0

1

 

 

д

 

 

 

 

 

Цифровая часть множителя [B]

b4 = 1

 

 

 

 

 

 

 

 

 

 

 

д

1

1

1

1

1

0

0

1

0

[A]

д

20 b4

b3 = 0

0

0

0

0

0

0

0

0

0

[A]

21 b3

д

b2 = 1

1

1

1

0

0

1

0

0

0

[A]

22 b2

д

b1 = 0

0

0

0

0

0

0

0

0

0

[A]

23 b1

д

 

1

1

0

1

1

1

0

1

0

Псевдопроизведение

 

0

1

1

1

0

0

0

0

0

Коррекция [-[A] ]

 

 

 

 

 

 

 

 

 

 

 

 

д д

 

0

1

0

0

1

1

0

1

0

Результат

[П]д = [A]д × [B]д = 0.10011010

Пример 10. [A]д = 0.1110

 

 

 

 

 

 

[B]д = 1.0101

 

 

 

 

 

 

 

 

 

 

 

0

1

1

1

0

 

 

 

 

 

 

.

0

1

0

1

b4 = 1

 

0

0

0

0

0

1

1

1

0

b3 = 0

0

0

0

0

0

0

0

0

0

b2 = 1

0

0

0

1

1

1

0

0

0

b1 = 0

0

0

0

0

0

0

0

0

0

 

 

0

0

1

0

0

0

1

1

0

 

1

0

0

1

0

0

0

0

0

 

 

1

0

1

1

0

0

1

1

0

[П]д = [A]д × [B]д = 1.01100110

 

 

Пример 11. [A]д = 1.0101

 

 

 

 

 

 

[B]д = 0.1110

 

 

 

 

 

 

 

 

 

 

 

1

0

1

0

1

 

 

 

 

 

 

.

1

1

1

0

b4 = 0

 

 

 

 

 

 

 

 

 

 

0

0

0

0

0

0

0

0

0

b3 = 1

1

1

1

1

0

1

0

1

0

b2 = 1

1

1

1

0

1

0

1

0

0

b1 = 1

1

1

0

1

0

1

0

0

0

 

 

1

0

1

1

0

0

1

1

0

[П]д = [A]д × [B]д = 1.01100110

 

 

Пример 12. [A]д = 0.1011

 

 

 

 

 

 

[B]д = 0.1110

 

 

 

 

 

 

 

 

 

 

 

0

1

0

1

1

 

 

 

 

 

 

.

1

1

1

0

b4 = 0

 

 

 

 

 

 

 

 

 

 

0

0

0

0

0

0

0

0

0

b3 = 1

0

0

0

0

1

0

1

1

0

b2 = 1

0

0

0

1

0

1

1

0

0

b1 = 1

0

0

1

0

1

1

0

0

0

 

 

0

1

0

0

1

1

0

1

0

[П]д = [A]д × [B]д = 0.10011010

Множимое [A]д

Цифровая часть множителя [B]д

[A]д 20 b4 [A]д 21 b3

[A]д 22 b2 [A]д 23 b1

Псевдопроизведение

Коррекция [-[A]д]д Результат

Множимое [A]д

Цифровая часть множителя [B]д

[A]д 20 b4

[A]д 21 b3 [A]д 22 b2

[A]д 23 b1

Результат

Множимое [A]д

Цифровая часть множителя [B]д

[A]д 20 b4 [A]д 21 b3 [A]д 22 b2

[A]д 23 b1

Результат

Как видим, умножение положительных чисел в дополнительном коде никаких особенностей не привносит по сравнению с умножением натуральных чисел (см. пример 2) за исключением присутствия знака в частичных произведениях.

б) Умножение с младших разрядов множителя и сдвигом суммы частичных произведений вправо

Выражение (6) является аналитической записью данного алгоритма умножения (только для цифровой части множителя без учета возможной коррекции результата):

[A]д×[B]д =((…((0 + [A]д bn) 2-1 + [A]д bn-1) 2-1 + … + [A]д b2) 2-1 + [A]д b1) 2-1 (6)

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

Пример 13. [A]д = 1.0010 [B]д = 1.0101

 

 

1

0

0

1

0

 

Множимое [A]д

 

 

 

 

 

 

 

.

0

1

0

1

 

Цифровая часть множителя [B]д

b4 = 1

1 1 0 0 1 0

 

 

 

 

0 + [А]м

b

4

= П

1

 

 

 

 

 

 

 

 

 

 

 

 

д

 

 

 

 

1

1

1

0

0

1

0

 

 

 

П1 2-1

 

 

 

 

 

b3 = 0

0 0 0 0 0 0

 

 

 

 

[А]мд b3

 

 

 

 

 

 

1

1

1

0

0

1

0

 

 

 

П

2-1+ [А]м b

3

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

д

2

 

1

1

1

1

0

0

1

0

 

 

П2 2-1

 

 

 

 

 

b2 = 1

1 1 0 0 1 0

 

 

 

 

[А]мд b2

 

 

 

 

 

 

 

 

 

 

2-1+ [А]м b

 

 

! → 1 0 1 1 1 0 1 0

 

 

П

2

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

д

3

 

1

1

0

1

1

1

0

1

0

 

П3 2-1

 

 

 

 

 

b1 = 1

0 0 0 0 0 0

 

 

 

 

[А]мд b1

 

 

 

 

 

 

1

1

0

1

1

1

0

1

0

 

П

2-1+ [А]м b

1

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

д

4

 

1

1

1

0

1

1

1

0

1

0

П 2-1 − псевдопроизведение

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

0

0

1

1

1

0

 

 

 

 

Коррекция [−[А]мд ]мД

 

0

0

1

0

0

1

1

0

1

0

Результат

 

 

 

 

 

[П]д = [A]д × [B]д = 0.10011010

Умножение в двоичной системе счисления

Для начала рассмотрим следующий любопытный факт. Для того, чтобы умножить двоичное число на 2 (десятичная двойка это 10 в двоичной системе) достаточно к умножаемому числу слева приписать один ноль.

Пример. 10101 * 10 = 101010

Проверка.

10101 = 1*24 + 0*23 + 1*22 + 0*21 +1*20 = 16 + 4 + 1 = 21

101010 =1*25 + 0*24 + 1*23 + 0*22 +1*21 +0*20 = 32 + 8 + 2 = 42

21 * 2 = 42

Если мы вспомним, что любое двоичное число разлагается по степеням двойки, то становится ясно, что умножение в двоичной системе счисления сводится к умножению на 10 (то есть на десятичную 2), а стало быть, умножение это ряд последовательных сдвигов. Общее правило таково: как и для десятичных чисел, умножение двоичных выполняется поразрядно. И для каждого разряда второго множителя к первому множителю добавляется один ноль справа. Пример (пока не столбиком):

1011 * 101 Это умножение можно свести к сумме трёх порязрядных умножений:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 В столбик это же самое можно записать так:

   
  *  
   
   
   

Примечание: Кстати таблица умножения в двоичной системе состоит только из одного пункта 1 * 1 = 1


Проверка:

101 = 5 (десятичное) 1011 = 11 (десятичное)

110111 = 55 (десятичное) 5*11 = 55 верное равенство

Решите самостоятельно:

а) 1101 * 1110 = _________________ б) 1010 * 110 = __________________

в) 1011 * 11 = _______________ г) 101011 * 1101 = _______________

д) 10010 * 1001 = __________________

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

Мы уже рассмотрели три действия и думаю уже понятно, что в общем-то действия над двоичными числами мало отличаются от действий над десятичными числами. Разница появляется только в том, что цифр две а не десять, но это только упрощает арифметические операции. Так же обстоит дело и с делением, но для лучшего понимания алгоритм деления разберём более подробно. Пусть нам необходимо разделить два десятичных числа, например 234 разделить на 7. Как мы это делаем.

Мы выделяем справа (от старшего разряда) такое количество цифр, чтобы получившееся число было как можно меньше и в то же время больше делителя. 2 — меньше делителя, следовательно, необходимое нам число 23. Затем делим полученное число на делитель с остатком. Получаем следующий результат:

   
-    
       

Описанную операцию повторяем до тех пор, пока полученный остаток не окажется меньше делителя. Когда это случится, число полученное под чертой, это частное, а последний остаток — это остаток операции. Так вот операция деления двоичного числа выполняется точно также. Попробуем

Пример: 10010111 / 101

                     

Ищем число, от старшего разряда которое первое было бы больше чем делитель. Это четырехразрядное число 1001. Оно выделено жирным шрифтом. Теперь необходимо подобрать делитель выделенному числу. И здесь мы опять выигрываем в сравнении в десятичной системой. Дело в том, что подбираемый делитель это обязательно цифра, а цифры у нас только две. Так как 1001 явно больше 101, то с делителем всё понятно это 1.

 
-              
                 

Итак, остаток от выполненной операции 100. Это меньше чем 101, поэтому чтобы выполнить второй шаг деления, необходимо добавить к 100 следующую цифру, это цифра 0. Теперь имеем следующее число:

 
-              
               
 
-            
               
  -              
                 

1000 больше 101 поэтому на втором шаге мы опять допишем в частное цифру 1 и получим следующий результат (для экономии места сразу опустим следующую цифру).

 

Полученное число 110 больше 101, поэтому и на этом шаге мы запишем в частное 1. Получиться так:

 
-          
               
  -              
                 
      -          
                   

Полученное число 11 меньше 101, поэтому записываем в частное цифру 0 и опускаем вниз следующую цифру. Получается так:

       
-              
                     
  -                    
                       
      -                
                       

Полученное число больше 101, поэтому в частное записываем цифру 1 и опять выполняем действия. Получается такая картина:

       
-            
                     
  -                    
                       
      -                
                       
          -            
                         

Полученный остаток 10 меньше 101, но у нас закончились цифры в делимом, поэтому 10 это окончательный остаток, а 1110 это искомое частное.

Проверим в десятичных числах

10010011 = 147 101 = 5

10 = 2 11101 = 29

   
-  
       
  -    
         

На этом мы заканчиваем описание простейших арифметических операций, которые необходимо знать, для того, чтобы пользоваться двоичной арифметикой, и теперь попробуем ответить на вопрос «Зачем нужна двоичная арифметика». Конечно, выше уже было показано, что запись числа в двоичной системе существенно упрощает арифметические операции, но в то же время сама запись становится значительно длиннее, что уменьшает ценность полученного упрощения, поэтому необходимо поискать такие задачи, решение которых существенно проще в двоичных числах.

Самостоятельная работа № 4

1. Выполните сложение, вычитание, умножение в двоичной системе счисления:

1.1111 и 1011;  
2.1001 и 110;  
3.11001 и 10111;  
4.111 и 101;  
5.10011 и 1101;  
6.10011 и 1001;  
7.110110 и 11111;  
8.10011001 и 1101;  
9.10101 и 1101;
10. 10111и 111;
11.11001и 111;
12.10111 и 111100;
13.11000 и 1101;
14.1011и 111.
15.1100100 и 100011;
16.101101 и 1101;
 
     

 

Ответ: __________________

2. Выполните деление в двоичной системе счисления:

  1. 10100101: 1011=
  2. 10100101:1111=
  3. 110110:110=
  4. 110110:1001=
  5. 1000111111:11001=
  6. 1000111111:10111=
  7. 11110111:10011=
  8. 11110111:1101=
  9. 10101011: 10011=
  10. 10101011: 1001=
  11. 10100001:111=
  12. 10100001:10111=
  13. 10101111:111=
  14. 10101111:11001=
  15. 1001101:1011=
  16. 1001101:111=

Ответ: __________________

Контрольная работа по теме «Системы счисления»

В-1.

№ 1.

Представьте в развернутой форме:

а) 4563 ; б) 100101 ;

№ 2.

Переведите число 75 из десятичной системы счисления в двоичную.

№ 3.

Выполните действия:

а) 11001101011 + 1110000101 ; б) 101011 – 10011 ; в) 1011 · 101 .

В-2.

№ 1

Представьте в развернутой форме:

а) 1563 ; б) 100111 ;

№ 2.

Переведите число 67 из десятичной системы счисления в двоичную.

№ 3.

Выполните действия:

а) 11001101111 + 1110000101 ; б) 10111 – 10011 ; в) 1111 · 101 .

В-3.

№ 1

Представьте в развернутой форме:

а) 2563 ; б) 110101 ;

№ 2.

Переведите число 59 из десятичной системы счисления в двоичную.

№ 3.

Выполните действия:

а) 11111101011 + 1110000111 ; б) 11111 – 10011 ; в) 10011 · 101 .

В-4.

№ 1

Представьте в развернутой форме:

а) 2573 ; б) 1010101 ;

№ 2.

Переведите число 95 из десятичной системы счисления в двоичную.

№ 3.

Выполните действия:

а) 11111101001 + 1110000111 ; б) 11101 – 10011 ; в) 10111 · 101 . Дополнительный раздел: «Занимательно и интересно!»

А) Рисуем по точкам.

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

Таблица 1

№ точки Координаты точки (X;Y)
X Y  
1002 102  
1012 1012  
12 1012  
112 10102  
1002 10102  
112 1102  
1012 1102  
1102 1012 + 1002  
1112 10012  
1102 1102  
1002 * 102 1102  
10002 1012  
1102 1012  
1012 102  

Б) Рождение цветка.

Понаблюдаем за рождением цветка: сначала появился один листочек, затем второй … и вот распустился бутон. Постепенно подрастая, цветок показывает нам некоторое двоичное число. Если вы до конца проследите за ростом цветка, то узнаете, сколько дней ему понадобилось, чтобы вырасти.

Ответ: ______________

В) Русская поговорка.

Здесь зашифрована известная русская поговорка. Прочитайте ее, двигаясь с помощью двоичных цифр в определенной последовательности.

 

Ответ: ____________________________________________

 

Для любознательных

Ещё два способа преобразования чисел 10-й в 2-ую систему счисления:

I. Метод вычитания

С детства мы считать учились – раз, два, три, четыре, пять

Десятичной ту систему мы привыкли называть.

Были палочки и счеты, калькулятор, Пифагор,

А теперь перед глазами – серебристый монитор.

Эта умная машина сможет все нам сосчитать

Ну, а как она считает – предстоит нам разобрать.

Мы считаем в десятичной – два, двенадцать, сто один,

А компьютер лишь в двоичной – либо ноль, либо один.

Разберемся на примере: число будет – сорок пять

Наибольшую здесь степень нам придется сосчитать

Раз считаем мы в двоичной основанье всегда два

Показатель мы находим от начального числа.

И поскольку изначально наша цифра сорок пять,

Мы подумаем и скажем показатель будет пять. В показателе пятерка в основанье цифра два Возведем мы двойку в степень и получим 32. Возвращаемся мы снова к нашей цифре 45 Нам теперь от этой цифры 32 нужно отнять.

Разность сосчитать нам просто мы уже не первый класс

Видим: циферка 13 получается у нас.

Теперь циферку 13 также как и 45

Вместе с вами нам придется разложить и посчитать

Снова в основанье двойка показатель будет три

Двойка в третьей будет восемь ну, а дальше сам смотри.

У 45-ти два в пятой умножаем на один

У 13 два в третьей тоже множим на один

Два в четвертой не встречалась, тут и нечего гадать

Значит, будем два в четвертой мы на нолик умножать.

Запись: 4510 = 1*25+0*24+1*23+1*22+0*21+1*20 =1011012

Подводим итог: Необходимо разложить данное нам число по степеням «2». В том случае, если полная степень «2» присутствует при разложении, сомножителем будет единица, если степени «2» нет – сомножитель ноль. Важно! При записи числа в «2»-ой системе счисления нельзя пропускать ни одну степень.

II. Метод степеней

Разберем еще один пример: Перевести из «10»-ой системы счисления в «2»-ю число 23. Какие степени «2» представлены в этом числе?

1) Ищем максимальную степень «2» – это 24 =16. Итак: 23-16=7

2) Для числа 7 подбираем максимальную степень это 22 =4. Вычитаем 7-4=3.

3) Для числа 3 подбираем максимальную степень это 21 =2. Вычитаем 3-2=1.

4) Для числа 1 остался единственный вариант это степень 20 =1.

Теперь можем записать разложение числа 23 по степеням «2»:

Запись: 2310 =1*24 +0*23 +1*22 +1*21 +1*20

 

 


Читайте также:


Рекомендуемые страницы:

Поиск по сайту

III . Умножение двоичных чисел. — Мегаобучалка

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

1. анализ цифры очередного разряда множителя;           

2. суммирование множимого с накопленной суммой частичных произведений, если цифра      множителя «1»;    

3. сдвиги в каждом такте умножения.

Умножение можно выполнять как с младших, так и со старших разрядов множителя, со сдвигом, как частичной суммы, так и множимого в процессе умножения. Этим объясняется существование четырех способов умножения чисел.

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

Задание №1 Знаки операндов: С>0, D <0. Представить числа в форме с ФЗ и перемножить их в прямом коде, используя 1 алгоритм умножения. Произвести проверку.

 

 

I способ — умножение с младших разрядов множителя со сдвигом суммы частичных произведений вправо.

Устройства, которые хранят операнды, регистры, имеют следующую разрядность:

1. регистры множителя и множимого – n-разрядные;

2. регистр частичных произведений – 2n-разрядный.

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

Особенность I способа умножения состоит в том, что имеется возможность временного переполнения разрядной сетки (ПРС) в регистре суммы частичных произведений, которое ликвидируется при очередном сдвиге вправо.



 

Алгоритм умножения двоичных чисел в прямом коде:

1. определить знак произведения путем сложения по модулю два знаковых разрядов сомножителей;

2. перемножить модули сомножителей одним из четырех способов;

3. присвоить полученному произведению знак из п.1. данного алгоритма.

C =  2310

D = -5710

 

С =   101112

D =  -1110012

С пк = 0,010111                 М = 26

D пк = 1,111001

 

D = 0,111001 – модуль множимого

Знак произведения: 0  + 1 = 1

 

Множитель            n Сумма ЧП          2n Примечания
,010111 0,000000 000000  
    0,111001 0,111001 000000 Сложение Сдвиг
,001011   0,011100 100000 0,111001 1,010101 100000 Сложение   Сдвиг
,000101     0,101010 110000 0,111001 1,100011 110000 Сложение   Сдвиг
,000010   0,110001 111000 0,011000 111100 Сдвиг Сдвиг
,000001 0,111001 1,010001 111100                     Сложение Сдвиг
,000000 0,101000 111110 0,010100 011111 Сдвиг

 

Масштаб произведения: М = 212

Ответ:

1, 010100 011111пк = -101 000 1111 12 = 131110

 

Проверка:

2310 * (-57)10 = 131110

 

 

Задание № 2 Знаки операндов: С<0, D >0. Представить числа в форме с ФЗ и перемножить их в дополнительном коде с автоматической коррекцией, используя 2 алгоритм умножения. Произвести проверку.

 

II способ — умножение с младших разрядов множителя со сдвигом множимого влево.

Устройства, которые хранят операнды, регистры, имеют следующую разрядность:

1. регистр множителя – n-разрядный;

2. регистры множимого и суммы частичных произведений – 2n-разрядный.

Первоначально множимое помещается в младшие разряды регистра, а затем в каждом такте сдвигается на один разряд влево.

 

Сложение, вычитание, умножение и деление в системах счисления

Сложение в системах счисления

Как мы складываем в десятичной системе счисления?

Давайте вспомним о том, как мы складываем числа уже привычным нам способом, в десятичной системе счисления.

Самое главное стоит понять разряды. Вспомните алфавит каждой СС и тогда вам станет легче.

Сложение в двоичной системе счисления

Сложение в двоичной системе ничем не отличается от сложения в десятичной системе. Главное помнить, алфавит содержит всего две цифры: 0 и 1. Поэтому когда мы складываем 1 + 1, то получаем 0, и увеличиваем число еще на 1 разряд. Посмотрите на пример выше:

  1. Начинаем складывать как и привыкли справа налево. 0 + 0 = 0, значит записываем 0. Переходим к следующему разряду.
  2. Складываем 1 + 1 и получаем 2, но 2 нет в двоичной системе счисления, а значит мы записываем 0, а 1 добавляем к следующему разряду.
  3. У нас получается в этом разряде три единицы складываем 1 + 1 + 1 = 3, этой цифры также быть не может. Значит 3 – 2 = 1. И 1 добавляем к следующему разряду.
  4. У нас вновь получается 1 + 1 = 2. Мы уже знаем, что 2 быть не может, значит записываем 0, а 1 добавляем к следующему разряду.
  5. Складывать больше нечего, значит в ответе получаем: 10100.

Один пример мы разобрали, второй решите самостоятельно:

Сложение в восьмеричной системе счисления

Так же как и в любых других системах счисления необходимо помнить Алфавит. Давайте попробуем сложить выражение.

  1. Все как обычно, начинаем складывать справа налево. 4 + 3 = 7.
  2. 5 + 4 = 9. Девяти быть не может, значит из 9 вычитаем 8, получаем 1. И еще 1 добавляем к следующему разряду.
  3. 3 + 7 + 1 = 11. Из 11 вычитаем 8, получаем 3. И единицу добавляем к следующему разряду.
  4. 6 + 1 = 7.
  5. Складывать далее нечего. Ответ: 7317.

А теперь проделайте сложение самостоятельно:

Сложение в шестнадцатеричной системе счисления

  1. Выполняем уже знакомые нам действия и не забываем про алфавит. 2 + 1 = 3.
  2. 5 + 9 = 14. Вспоминаем Алфавит: 14 = Е.
  3. С = 12. 12 + 8 = 20. Двадцати нет в шестнадцатеричной системе счисления. Значит из 20 вычитаем 16 и получаем 4. И единицу добавляем к следующему разряду.
  4. 1 + 1 = 2.
  5. Больше складывать нечего. Ответ: 24Е3.

Вычетание в системах счисления

Вычитание в десятичной системе счисления

Вспомним, как мы это делаем в десятичной системе счисления.

  1. Начинаем слева направо, от меньшего разряда к большему. 2 – 1 = 1.
  2. 1 – 0 = 1.
  3. 3 – 9 = ? Тройка меньше девяти, поэтому позаимствуем единицу из старшего разряда. 13 – 9 = 4.
  4. Из последнего разряда мы взяли единицу для предыдущего действия, поэтому 4 – 1 = 3.
  5. Ответ: 3411.

Вычитание в двоичной системе счисления

  1. Начинаем как обычно. 1 – 1 = 0.
  2. 1 – 0 = 1.
  3. От 0 отнять единицу нельзя. Поэтому заберем один разряд у старшего. 2 – 1 = 1.
  4. Ответ: 110.

А теперь решите самостоятельно:

Вычитание в восьмеричной системе счисления

  1. Ничего нового, главное помнить алфавит. 4 – 3 = 1.
  2. 5 – 0 = 5.
  3. От 3 отнять 7 мы сразу не можем, для этого нам необходимо заимствовать единицу у более старшего разряда. 11 – 7 = 4.
  4. Помним, что заимствовали единицу ранее, 6 – 1 = 5.
  5. Ответ: 5451.

Пример для самостоятельного решения:

Вычитание в шестнадцатеричной системе счисления

Возьмем предыдущий пример, и посмотрим каков будет результат в шестнадцатеричной системе. Такой же или другой?

  1. 4 – 3 = 1.
  2. 5 – 0 = 5.
  3. От 3 отнять 7 мы сразу не можем, для этого нам необходимо заимствовать единицу у более старшего разряда. 19 – 7 = 12. В шестнадцатеричной системе 12 = С.
  4. Помним, что заимствовали единицу ранее, 6 – 1 = 5
  5. Ответ: 5С51

Пример для самостоятельного решения:

Умножение в системах счисления

Умножение в десятичной системе счисления

Давайте запомним раз и навсегда, что умножение в любой системе счисления на единицу, всегда даст тоже самое число.

  1. Каждый разряд умножаем на единицу, как обычно справа налево, и получаем число 6748;
  2. 6748 умножаем на 8 и получаем число 53984;
  3. Проделываем операцию умножения 6748 на 3. Получаем число 20244;
  4. Складываем все 3 числа, по правилам. Получаем 2570988;
  5. Ответ: 2570988.

Умножение в двоичной системе счисления

В двоичной системе умножать очень легко. Мы всегда умножаем либо на 0, либо на единицу. Главное, это внимательно складывать. Давайте попробуем.

  1. 1101 умножаем на единицу, как обычно справа налево, и получаем число 1101;
  2. Проделываем эту операцию еще 2 раза;
  3. Складываем все 3 числа внимательно, помним про алфавит, не забывая про лесенку;
  4. Ответ: 1011011.

Пример для самостоятельного решения:

Умножение в восьмеричной системе счисления

Есть небольшой лайфхак, как считать в восьмеричной системе. Давайте рассмотрим на примере:

  1. 5 х 4 = 20. А 20 = 2 х 8 + 4. Остаток от деления записываем в число – это будет 4, а 2 держим в уме. Проделываем эту процедуру справа налево и получаем число 40234;
  2. При умножении на 0, получаем четыре 0;
  3. При умножении на 7, у нас получается число 55164;
  4. Теперь складываем числа и получаем – 5556634;
  5. Ответ: 5556634.

Пример для самостоятельного решения:

Умножение в шестнадцатеричной системе счисления

Все как обычно, главное вспомните алфавит. Буквенные цифры, для удобства переводите в привычную для себя систему счисления, как умножите, переводите обратно в буквенное значение.

Давайте для наглядности разберем умножение на 5 числа 20А4.

  1. 5 х 4 = 20. А 20 = 16 + 4. Остаток от деления записываем в число – это будет 4, а 1 держим в уме.
  2. А х 5 + 1 = 10 х 5 + 1 = 51. 51 = 16 х 3 + 3. Остаток от деления записываем в число – это будет 3, а 3 держим в уме.
  3. При умножении на 0, получаем 0 + 3 = 3;
  4. 2 х 5 = 10 = А; В итоге у нас получается А334; Проделываем эту процедуру с двумя другими числами;
  5. Помним правило умножения на 1;
  6. При умножении на В, у нас получается число 1670С;
  7. Теперь складываем числа и получаем – 169В974;
  8. Ответ: 169В974.

Пример для самостоятельного решения:

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

С делением все так же, как и в привычной нам десятичной системе счисления.

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

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

  1. Сколько в 101 получится 11? Правильно, 1. 101 – 11 = 10;
  2. 100 / 11? Так же 1 раз 11 поместится в 100. 100 – 11 = 1;
  3. 11 / 11 = 1, в остатке 0;
  4. Ответ: 111.

Деление в восьмеричной системе счисления

  1. 46 меньше 53, значит делить будем 462. Надо угадать сколько раз число 53 поместиться? Угадываем 7 и записываем;
  2. 53 / 53 = 1. Записываем к ответу, в остатке у нас 0;
  3. Последний 0 мы так же записываем к ответу, так как делить больше нечего;
  4. Ответ: 710.

Деление в шестнадцатеричной системе счисления

Осталось самое страшное – это научиться делить в шестнадцатеричной системе. Да прибудет с нами сила.

  1. 4С мы должны поделить на 2В. Методом подбора определяем что умножить можем только 1 раз. 4С – 2В = 21 и единицу записываем в ответ;
  2. Также методом подбора определяем, что 2В, мы можем умножить на С. 219 – 204 = 15;
  3. Опять, методом подбора определяем, что это 8. 158 – 158 = 0, решение закончено;
  4. Ответ: 1С8.

Умножение двоичных чисел

Умножение двоичных чисел

Представлено руководство о том, как умножать двоичные числа, а также примеры, упражнения и ответы.

Пользовательский поиск


Сложить двоичные числа с одной цифрой

давайте сначала сложим двоичные числа с одной цифрой.
0 х 0 = 0
0 х 1 = 1
1 х 0 = 1
1 х 1 = 1
Вышеупомянутые простые добавления аналогичны десятичным.

Умножение двоичных чисел

Теперь мы умножаем числа, состоящие более чем из одной цифры: 1 0 1 1 x 1 0 0 1

Умножение двоичных чисел похоже на умножение десятичных чисел.

1 0 1 1
х
1 0 0 1
____ ____ ____ ____
1 0 1 1
0 0 0 0
0 0 0 0
1 0 1 1
___ ___ ___ ___ ___ ___ ___
1 1 0 0 0 1 1

Умножение двоичных чисел производится сдвигом на один бит и сложением.Можно легко проверить, что 1011, которое равно 11 в десятичном виде, умноженное на 1001, которое равно 9 в двоичном формате, дает 99, что составляет 1100011 в двоичном формате.

Упражнения

А) Умножьте двоичные числа.
  1. 111 х 11
  2. 1011 х 111
  3. 10101 х 1101
  4. 100011 x 1100011 (нужно знать, что 1 + 1 + 1 + 1 = 100 переносить 10)

Ответы на вышеуказанные упражнения

  1. 111 х 11 = 10101
  2. 1011 х 111 = 1001101
  3. 10101 х 1101 = 100010001
  4. 100011 x 1100011 = 110110001001

двоичных чисел ← Информатика отключена

Двоичная система счисления играет центральную роль в том, как информация всех видов хранится на компьютерах.Понимание двоичного кода может снять большую загадку с компьютеров, потому что на фундаментальном уровне они на самом деле просто машины для включения и выключения двоичных цифр. В этом документе есть несколько упражнений с двоичными числами, достаточно простых, чтобы их можно было использовать для обучения двоичной системе любого, кто умеет считать! Обычно дети очень быстро изучают двоичную систему, используя этот подход, но мы обнаруживаем, что многие взрослые также взволнованы, когда они наконец понимают, что такое биты и байты на самом деле.

Описание деятельности (PDF)

Переводов и других версий:

Видео


Фото

Связанные ресурсы

  • Более старую версию этого упражнения можно загрузить в формате PDF здесь. Содержание похоже на текущую версию, но есть некоторая дополнительная техническая информация.
  • Другие занятия и уроки:
      • Try Engineering занимается следующими видами деятельности:
        • Попробуйте двоичный файл! : в котором исследуется, как работают двоичные коды, как они применяются компьютерными инженерами к компьютерам и другому электронному оборудованию, включая часы.Студенты узнают, как использовать код, читать двоичные часы, а продвинутые студенты могут построить свои собственные двоичные часы из набора.
        • Mountain Rescue: Это простое упражнение для визуализации системы связи. Для этого студенты кодируют, декодируют, передают, получают и хранят сообщения. Для этого они будут использовать кодовую таблицу и фонарик. Они также будут вести лист хранения, из которого они могут извлекать информацию по мере необходимости.
      • Центр инноваций в преподавании математики также предлагает руководства для учителей по следующим темам:
      • Информатика и инженерия для K-12 (cse4k12.org) выполняет следующие действия, связанные с двоичными числами, указанными ниже:
        • Растровые изображения Действие, при котором растровые изображения представляют собой способ кодирования черно-белых изображений с использованием двоичных чисел. «0» используется для обозначения белого квадрата на изображении, а «1» используется для обозначения черного квадрата. Эти рабочие листы представляют собой набор сеток 8 × 8, где учащийся может рисовать свои собственные черно-белые изображения, а затем записывать соответствующие двоичные (и шестнадцатеричные) значения.
        • Crossbin Puzzles Задание аналогично кроссвордам, за исключением того, что подсказки представляют собой шестнадцатеричные числа, а ответы — двоичные числа («0» и «1») вместо слов.Кроме того, как только головоломка будет завершена, если вы заполните все квадраты «1» черным, вы увидите маленькую картинку или узор.
        • Perfect Shuffles Упражнение: если вы хотите взять верхнюю карту в колоде и перетасовать ее в определенную позицию, все, что вам нужно знать, это двоичное представление позиции, в которую вы хотите поместить карту. Затем вы выполняете последовательность идеальных перетасовок «вход» и «выход» на основе двоичного числа, и карта будет перетасована в желаемое место.
        • Binary Magic Trick: Набор из 6 карточек для простого магического трюка, в котором вы можете правильно угадать секретное число, выбранное учеником.Чтобы понять, как работает этот трюк, необходимо знать двоичный код
        • .
      • Веб-сайт Mathmaniacs имеет аналогичную деятельность (урок 1). Он включает в себя упражнение на двоичное фортепиано, которое является еще одним отличным подспорьем для изучения двоичных чисел (модифицированная версия Университета Кентербери доступна здесь). У математиков тоже есть волшебный трюк, который можно выполнять с двоичными числами.
      • У Рика Гарликова есть статья об обучении двоичных чисел с помощью сократовского диалога. Такой подход дает учащимся большие возможности, и общий принцип может применяться ко многим видам деятельности Unplugged.
      • CS4FN занимается деятельностью, связанной с размножением французских крестьян, под названием «Код французского крестьянина и код Грея». Решение проблемы блокировки на самом деле известно компьютерным ученым как код Грея: код, используемый в современном цифровом телевидении. Как бы то ни было, по своей физической форме все варианты головоломки с замками имеют одинаковое решение и логически (а значит, и их решения алгоритмически) идентичны. Решите один, и вы решите их все (компьютерные ученые любят использовать этот трюк с проблемами!)
      • У Стива Уаллина есть интересное упражнение под названием «Числа», в котором нужно записать все возможные числа, которые могут быть получены из битовых комбинаций от 0000 до 1111.
      • На странице головоломки находится двоичная головоломка с перекрестными числами. Эта головоломка полностью состоит из двоичных чисел, поэтому все символы, необходимые для заполнения квадратов, будут нулем или единицей. Кроссворд представляет собой квадратную сетку 4 × 4, поэтому все числа будут записаны в двоичной системе с 4 цифрами; например, 1 будет 0001, 2 будет 0010 и 4, 0100. Операция NOT изменяет все 0 на 1 и все 1 на 0; например, НЕ (0110) равно 1001, а НЕ (1010) равно 0101.
      • nrich Maths предлагает следующие задания с примечаниями и решениями:
      • DJ Dates предлагает забавное занятие по созданию колеса двоичного декодера, которое предоставляет студентам быстрый способ найти двоичное число и узнать букву, которую представляет двоичное число.В классе я раздаю студентам три распечатанных кусочка картона, и каждый студент вырезает и собирает свое собственное колесо двоичного декодирования:
  • Если вы хотите узнать больше:
      • Другие системы счисления в Википедии:
        • Десятичная система счисления: десятичная система счисления (также называемая десятичной системой счисления или иногда десятичной) имеет основу десять. Позиционные десятичные системы включают ноль и используют символы (называемые цифрами) для десяти значений (0, 1, 2, 3, 4, 5, 6, 7, 8 и 9) для представления любого числа, независимо от его размера и размера. небольшой.
        • Шестнадцатеричный: использует шестнадцать различных символов, чаще всего символы 0–9 для представления значений от нуля до девяти и A, B, C, D, E, F (или альтернативно от a до f) для представления значений от десяти до пятнадцати.
        • Octal: восьмеричная система счисления, или для краткости oct, представляет собой систему счисления с основанием 8 и использует цифры от 0 до 7. Цифры могут быть составлены из двоичных чисел путем группирования последовательных двоичных цифр в группы по три (начиная справа). ).
        • ASCII: Американский стандартный код для обмена информацией (акроним: ASCII; произносится / ˈæski /, ASS-kee) [1] — это схема кодирования символов, основанная на упорядочении английского алфавита.Коды ASCII представляют текст в компьютерах, коммуникационном оборудовании и других устройствах, использующих текст.
      • Технологический институт штата Вирджиния, Департамент компьютерных наук, имеет полный модуль по системам счисления.
      • [Требуется Flash-плеер] На факультете компьютерных наук Университета Теннесси есть вводный модуль CS, предназначенный для обучения следующим концепциям с использованием двоичных чисел с помощью анимации. Примечание. Этот сайт лучше всего просматривать в Internet Explorer:
      • У Кена Бигелоу есть веб-сайт Digital Logic, который охватывает большинство тем, связанных с двоичной и цифровой логикой.
      • У Джереми Фалкона есть отличная статья об обучении двоичному и шестнадцатеричному форматам.
      • Exploring Binary содержит следующие интересные разделы о способностях двойки:
        • Силы двух: почему они называются степенями двух? Какую картину вы видите? Каким образом набор описывается математически? Что входит в состав набора? Мы ответим на эти вопросы в этой статье.
        • 1 073 741 823 Зерна риса: В детской книге «Одно зерно риса: математическая сказка» девочка использует свои знания об экспоненциальном росте, чтобы обмануть жадного короля и заставить его перевернуть свои запасы риса.В истории скрыты математические концепции, связанные с удвоением: степени двойки, геометрические последовательности, геометрические ряды и показатели. Я проанализирую рассказ с этой точки зрения, а затем расскажу о своем опыте чтения его ученикам первого и третьего класса.
        • Исследование двоичных чисел с помощью калькулятора PARI / GP: PARI / GP — это сложный инструмент, состоящий из нескольких компонентов, но при этом его легко установить и использовать. В частности, я использую его командную оболочку, калькулятор PARI / GP, или сокращенно gp. Я покажу вам, как использовать простые команды gp для изучения двоичных чисел.
        • Степени двойки в задаче Иосифа Флавия: Эта формула, как вы не удивитесь, связана со степенью двойки и двоичными числами. Я расскажу о своем любимом решении, основанном на степени двойки.
        • Элементы двоичного кода в баскетбольном турнире NCAA: если вы похожи на меня, вы также думаете о степенях двойки, двоичных деревьях, логарифмах, законах экспонент, геометрических последовательностях, геометрических рядах и испытаниях Бернулли — короче говоря, об элементах двоичные числа, двоичный код и двоичную логику.
      • У доктора Джона Х. Линхарда есть следующие интересные статьи по истории различных основ счисления:
      • инструкции иллюстрируют счет двоичными числами с помощью мультфильмов:
      • У Керри Редшоу есть веб-сайт с информацией о пионерах в истории вычислительной техники. Представляют интерес следующие статьи:
      • Страница Hierosolyma Kadathian, посвященная системам счисления, определяет системы счисления, а затем предоставляет информацию о двоичной и шестнадцатеричной системе.
      • Math Steps — это хорошее объяснение и ресурсы для учителей по Place Values.
      • В журнале NCETM Seconday Magazine есть следующие интересные статьи:
        • Сосредоточьтесь на… маневрировании, статья о применении двоичной системы счисления, в которой задача состоит в том, чтобы переставить железнодорожные тележки с минимально возможным количеством маневров, и предоставляет ситуации, в которых учитель может сосредоточиться на некоторых конкретных способах математических действий
        • Сосредоточьтесь на… идеальном перемешивании: Есть несколько фокусов, в которых используется довольно сложная математика … и … маги могут идеально перемешать колоду карт.Изучите ссылку на Двоичные числа в этом упражнении
        • Исследование цифровых устройств: исследование чисел с основанием 2
  • Преобразователи чисел и калькуляторы:
  • Видео:
    • У Ви Харта есть видео: Binary Hand Dance, еще один интересный способ представить Binary!
    • Как стиль Каннам сломал YouTube — Computerphile
    • Студенты Даниэлы Маргиту запрограммировали это занятие в Робо-лагере Обернского университета.Посмотрите видео: проект RoboCamp Spring 2010 Robotics and CSUnplugged Binary Numbers Project
    • Абдулла Седдик (MIT Blossoms) имеет системы подсчета с руководствами для учителей и дополнительными ресурсами. Это видео призвано объяснить системы счета (десятичные, двоичные, шестнадцатеричные). Студенты узнают, как преобразовывать числа между этими системами. Также студенты узнают, как выполнять некоторые операции на уровне байтов и битов. Они будут использовать приложение Visual Basic (VB), которое изменяет цвета с помощью логических операций с числами.См. Также Волшебное изображение: стеганография в растровых файлах
    • Hanan Al Arfaj (MIT Blossoms) предлагает дополнительный урок «Почтальон и пять пакетов: пакеты данных и скорость передачи данных» с руководствами для учителей и дополнительными ресурсами. Это видео призвано объяснить процесс передачи данных в компьютерных системах и форму, в которую они передаются. Предварительные требования к этому уроку включают в себя некоторое знание концепции цифровых данных и понимание единиц размера файла (биты, байты, килобайты и т. Д.).
    • Пит Хоукс демонстрирует свою бинарную перчатку, где каждый палец представляет значение бита в простой двоичной последовательности: 1, 2, 4, 8 и 16. Датчики давления на концах каждого пальца регистрируют каждый бит как включенный или выключенный.
    • Аттическая академия имеет основы двоичного кода
    • Университет Рутгерса CS имеет функцию подсчета осьминогов: посмотрите, как каждое щупальце представляет собой один бит. Восемь щупалец = восемь степеней двойки! Отличный способ научить студентов изучать основы двоичной арифметики.

Ссылки на учебные программы

Великие принципы информатики [информация]
Учебный план ACM K12 [информация]
  • Уровень I (классы K – 2) Тема 11: Понять, как можно использовать нули и единицы для представления информации, такой как цифровые изображения и числа.
New Zealand Curriculum [информация]
    • Математика Уровень 2: Положение и ориентация
        • Найдите правила для следующего элемента в последовательном шаблоне.
      • Обобщите, что целые числа можно разделить разными способами.
    • Математика Уровень 3: Паттерны и отношения
        • Соедините элементы последовательных шаблонов с их порядковым номером и используйте таблицы, графики и диаграммы, чтобы найти взаимосвязи между последовательными элементами числовых и пространственных шаблонов.
      • Обобщите свойства сложения и вычитания с целыми числами.
  • Технологический уровень 3: Технологические системы
    • Поймите, что технологические системы представлены символическими языковыми инструментами, и поймите роль, которую играет «черный ящик» в технологических системах.

Числовые основы: введение и двоичные числа

Purplemath

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

MathHelp.com

В нашей обычной десятичной системе у нас есть цифры для чисел от нуля до девяти. У нас нет однозначного числа для «десяти». (Римляне использовали иероглиф «X».) Да, мы пишем «10», но это означает «1 десять и 0 единиц». Это две цифры; у нас нет ни одной единственной цифры, обозначающей «десять».

Вместо этого, когда нам нужно считать на единицу больше девяти, мы обнуляем столбец единиц и добавляем единицу к столбцу десятков. Когда мы становимся слишком большими в столбце десятков — когда нам нужно на один больше, чем девять десятков и девяти единиц («99»), мы обнуляем столбцы десятков и единиц и добавляем единицу к десятикратным или сотням. , столбец. Следующий столбец — это столбец десять раз десять, или тысячи. И так далее, причем каждый столбец большего размера в десять раз больше предыдущего. Мы помещаем цифры в каждый столбец, сообщая нам, сколько копий этой степени десяти нам нужно.

Единственная причина, по которой математика по основанию десять кажется «естественной», а другие — нет, состоит в том, что вы использовали десятичную систему с детства. И (почти) каждая цивилизация использовала математику по основанию десять, вероятно, по той простой причине, что у нас десять пальцев. Если бы вместо этого мы жили в мультипликационном мире, где у нас было бы только четыре пальца на каждой руке (считайте их в следующий раз, когда вы смотрите телевизор или читаете комиксы), тогда «естественной» базовой системой, вероятно, была бы система с основанием восемь, или «восьмеричный».

двоичный

Давайте посмотрим на числа с основанием два или двоичные числа. Как бы вы записали, например, 12 10 («двенадцать по основанию десять») в виде двоичного числа? Вам нужно будет преобразовать в столбцы с основанием два, аналог столбцов с основанием десять. В десятичной системе координат у вас есть столбцы или «места» для 10 0 = 1, 10 1 = 10, 10 2 = 100, 10 3 = 1000 и так далее. Точно так же в основании два у вас есть столбцы или «места» для 2 0 = 1, 2 1 = 2, 2 2 = 4, 2 3 = 8, 2 4 = 16 и т. вперед.

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

Тройка в основании два на самом деле означает «1, два и 1, один», поэтому записывается как 11 2 .«Четыре» на самом деле означает дважды два, поэтому мы обнуляем столбец двоек и столбец единиц и помещаем «1» в столбец четверок; 4 10 записывается в двоичной форме как 100 2 . Вот список первых чисел:

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

  • Преобразует 101100101 2 в соответствующее десятичное число.

Я перечислю цифры по порядку, так как они появляются в номере, который они мне дали. Затем в другом ряду я отсчитываю эти цифры от ПРАВА, начиная с нуля:

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

1 × 2 8 + 0 × 2 7 + 1 × 2 6 + 1 × 2 5 + 0 × 2 4 + 0 × 2 3 + 1 × 2 2 + 0 × 2 1 + 1 × 2 0

= 1 × 256 + 0 × 128 + 1 × 64 + 1 × 32 + 0 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1

= 256 + 64 + 32 + 4 + 1

= 357

Затем 101100101 2 преобразуется в 357 10 .


Преобразование десятичных чисел в двоичные почти так же просто: просто разделите на 2.

  • Преобразует 357 10 в соответствующее двоичное число.

Чтобы выполнить это преобразование, мне нужно несколько раз делить на 2, отслеживая остатки по ходу дела. Смотрите ниже:

Приведенный выше рисунок анимирован на «живой» веб-странице.

Как видите, после многократного деления на 2 я получил следующие остатки:

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

357 10 преобразуется в 101100101 2 .


Партнер


Этот метод преобразования работает для преобразования в любое недесятичное основание. Только не забудьте поставить эту первую цифру вверху перед списком остатков. Если вам интересно, объяснение того, почему этот метод работает, доступно здесь.

Вы можете преобразовать десятичную систему счисления в любую другую. Когда вы изучаете эту тему в классе, вы, вероятно, должны будете преобразовывать числа в различные другие основы, поэтому давайте рассмотрим еще несколько примеров …


URL: https://www.purplemath.com/modules/numbbase.htm

Таблицы умножения в двоичной системе — The Reflective Educator

Двоичное число — это число, записанное в формате с основанием 2, например 101010101111.Двоичная система счисления удобна, потому что ее можно легко связать с логическими операторами, используемыми в схемах, и поэтому почти все современные компьютеры используют этот формат для связи.

Мы используем десятичную систему для общения в повседневной жизни, потому что она связана с нашей исходной системой счисления, и вся эта система была разработана, потому что у нас десять пальцев между двумя руками.

Чтобы преобразовать десятичное число в двоичное, мы хотим переписать десятичное число как сумму степеней двойки.Например, число 5 равно 4 + 1 или 2 2 + 2 0 , что совпадает с 1 × 2 2 + 0 × 2 1 + 1 × 2 0 . В двоичном формате мы записываем 5 как 101, поскольку это коэффициенты при степенях двойки ( Попробуйте это приложение , которое позволяет переключаться между двоичными и десятичными числами).

Вот основная таблица умножения для двоичной системы, которая включает только 0 и 1, так как это единственные цифры, которые вы должны умножать в двоичной системе (в десятичной системе вам нужна гораздо большая таблица умножения, так как вам нужно иметь возможность умножьте каждую из 10 разных цифр, 0–9, на каждую из 10 разных цифр).

Сравните это с традиционной таблицей умножения 10 на 10 для десятичных чисел.


(Изображение предоставлено: valilouve )

Если вы хотите умножать числа в двоичном формате, вы можете использовать некоторые стратегии, аналогичные обычному десятичному умножению. Например, 10101 умножить на 101 выглядит так:

Если вы хотите дважды проверить, 10101 совпадает с 1 × 2 4 + 0 × 2 3 + 1 × 2 2 + 0 × 2 1 + 1 × 2 0 = 16 + 0 + 4 + 0 + 1 = 21 и 101 равно 5 (как мы отмечали ранее), поэтому это умножение в десятичном виде составляет 21 × 5, что составляет 105.1101001 = 1 × 2 6 + 1 × 2 5 + 0 × 2 4 + 1 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0 = 64 + 32 + 8 + 1 = 105. Более подробный пример двоичного умножения можно найти на этом веб-сайте .

Смысл этого упражнения в том, что вы взяли что-то, что сложно сделать (запомнить таблицу умножения 10 на 10), и переключили его на что-то, что концептуально более сложно, но легче запомнить.Для меньших чисел быстрее умножать непосредственно в десятичном виде, но для больших чисел фактически потребуется меньше времени, чтобы преобразовать их в двоичную форму, выполнить умножение и преобразовать обратно. Вы можете заметить, что сам шаг умножения намного проще, чем десятичное умножение, поскольку это просто вопрос запоминания 2 фактов (0 × 0 = 0 и 0 × 1 = 1) и правильного выравнивания чисел, чтобы их значение соответствовало разряду. Посетите эту страницу для получения дополнительной информации об операциях с двоичными числами.

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

Двоичное умножение — Скачать PDF бесплатно

Инварианты цикла и двоичный поиск

Инварианты цикла и двоичный поиск Глава 4.3.3 и 9.3.1-1 — Краткое описание Ø Итерационные алгоритмы, утверждения и доказательства правильности Ø Двоичный поиск: пример из практики — 2 — Краткое описание Ø Итерационные алгоритмы, утверждения

Дополнительная информация

Факторизация в кольцах многочленов

Факторизация в кольцах многочленов Эти заметки представляют собой краткое изложение некоторых важных моментов о делимости в кольцах многочленов из 17 и 18 Современной абстрактной алгебры Галлиана.Самые важные

Дополнительная информация

Алгоритмы факторинга

Алгоритмы факторинга Метод p 1 и квадратичное решето 17 ноября 2008 г. () Алгоритмы факторинга 17 ноября 2008 г. 1/12 Метод факторинга Ферма Ферма заметил, что если n имеет два множителя,

Дополнительная информация

Домашнее задание до теста №2

MATh41: Домашнее задание по теории чисел до теста № Филипп БРАУН Раздел 3.1 стр. 43, 1. Было высказано предположение, что существует бесконечно много простых чисел вида n. Покажите пять таких простых чисел. Решение. Пять таких

Дополнительная информация

Алгоритм двоичного поиска

Алгоритм двоичного поиска Определение Поиск в отсортированном массиве путем многократного деления интервала поиска пополам. Начните с интервала, охватывающего весь массив. Если значение ключа поиска меньше

Дополнительная информация

8 Делимость и простые числа

8 Делимость и простые числа 8.1 Делимость В этом коротком разделе мы расширяем понятие кратного с натуральных чисел до целых. Мы также суммируем несколько других терминов, которые выражают

Дополнительная информация

легко видеть, что α = a

21. Кольца многочленов Обратим теперь внимание на определение простых элементов кольца многочленов, где кольцо коэффициентов является полем. Мы уже знаем, что такое кольцо многочленов является UF.Следовательно,

Дополнительная информация

Конспект лекций по линейному поиску

Конспект лекции по линейному поиску 15-122: Принципы императивных вычислений Фрэнк Пфеннинг Лекция 5 29 января 2013 г. 1 Введение Одна из фундаментальных и повторяющихся проблем в информатике — это

Дополнительная информация

3. Математическая индукция.

3.МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ 83 3. Математическая индукция 3.1. Первый принцип математической индукции. Пусть P (n) — предикат с областью дискурса (над) натуральными числами N = {0, 1 ,, …}. Если (1)

Дополнительная информация

Смешанный двоичный алгоритм Евклида

Электронные заметки по дискретной математике 35 (009) 169 176 www.elsevier.com/locate/endm Смешанный двоичный алгоритм Евклида Сиди Мохамед Седжелмачи LIPN CNRS UMR 7030 Université Paris-Nord Av.Ж.-Б. Клеман,

Дополнительная информация

CS473 — Алгоритмы I

CS473 — Алгоритмы I Лекция 4 Парадигма дизайна «Разделяй и властвуй» Просмотр в режиме слайд-шоу 1 Напоминание: Сортировка слиянием Входной массив Сортировка этой половины Сортировка этой половины Divide Conquer слияние двух отсортированных половин Объединить

Дополнительная информация

Математическая индукция

Математическая индукция В логике мы часто хотим доказать, что каждый член бесконечного множества имеет какую-то особенность.Например, мы хотели бы показать: N 1: это число 1: имеет функцию Φ (x) (n 1 x! 1 x) Каким образом

Дополнительная информация

Глава R.4 Факторинговые многочлены

Глава R.4 Факторинг полиномов Введение в факторинг Факторинг выражения означает, что выражение должно быть записано как произведение двух или более факторов. Пример задачи: разложите каждое выражение на множители. а. 15 б. х

Дополнительная информация

Примеры индукционных доказательств

Рабочий лист по математике 3: индукционные доказательства III, образцы доказательств A.Примеры индукционных доказательств Дж. Хильдебранда Ниже приведены модельные решения некоторых практических задач на рабочих листах индукции. Решения, данные

Дополнительная информация

Лекция 13 — Основы теории чисел.

Лекция 13 — Основы теории чисел. Боаз Барак 22 марта 2010 г. Делимость и простые числа Если в этой лекции не указано иное, все числа являются целыми неотрицательными числами. Мы говорим, что A делит B, обозначается

Дополнительная информация

Автоматы и формальные языки

Автоматы и формальные языки Зима 2009-2010 гг. Яков Хель-Ор 1 О чем этот курс Этот курс посвящен математическим моделям вычислений Мы будем изучать различные модели машин (конечные автоматы,

Дополнительная информация

Факторинг и примитивность

Факторинг и примитивность Лектор: Димитрис Пападопулос В этой лекции мы обсудим проблему целочисленной факторизации и проверки на простоту, две проблемы, которые были в центре внимания большого количества людей. Дополнительная информация

csci 210: Рекурсия структур данных

csci 210: Сводка рекурсии структур данных Темы Обзор рекурсии простые примеры Прокладка Серпинского Башни Ханоя Проверка капли ЧИТАТЬ: Глава 3 учебника GT.5 Рекурсия В общем, метод определения

Дополнительная информация

минимальный полиономиальный пример

Минимальные многочлены Определение Пусть α — элемент из GF (p e). Мы называем монический многочлен наименьшей степени, который имеет коэффициенты в GF (p) и α в качестве корня, минимальным многочленом α. Пример: We

Дополнительная информация

Позиционная система нумерации

ПРИЛОЖЕНИЕ B Система позиционной нумерации В системе позиционной нумерации используется набор символов.Однако значение, которое представляет каждый символ, зависит от его номинальной стоимости и его разряда, связанного значения

. Дополнительная информация

6.2 Продолжение перестановок

6.2. Продолжение перестановок Теорема Перестановка на конечном множестве A является либо циклом, либо может быть выражена как произведение (композиция непересекающихся циклов. Доказательство проводится с помощью (сильной индукции по числу r из

Дополнительная информация

РАЗДЕЛ 10-2 Математическая индукция

73 0 Последовательности и серии 6.Приблизительно e 0. с использованием первых пяти членов ряда. Сравните это приближение с оценкой е 0 .. 6. Приблизительно е 0,5, используя первые пять членов

Дополнительная информация

~ ЭКВИВАЛЕНТНЫЕ ФОРМЫ ~

~ ЭКВИВАЛЕНТНЫЕ ФОРМЫ ~ Критически важным для понимания математики является концепция эквивалентных форм. В этом курсе используются эквивалентные формы. В математике встречаются эквивалентные формы

. Дополнительная информация

Линейные пороговые единицы

Единицы измерения линейного порога w x hx (… w n x n w Мы предполагаем, что каждая характеристика x j и каждый вес w j является действительным числом (мы ослабим это позже). Мы изучим три различных алгоритма для обучения линейному

Дополнительная информация

Булева алгебра, часть 1

Булева алгебра, часть 1 Page 1 Цели булевой алгебры Понимание базовой булевой алгебры Связывание булевой алгебры с логическими сетями Доказательство законов с использованием таблиц истинности Понимание и использование первых основных теорем

Дополнительная информация

РАЗМЕР ВЕКТОРНОГО ПРОСТРАНСТВА

ИЗМЕРЕНИЕ ВЕКТОРНОГО ПРОСТРАНСТВА КИТ КОНРАД Этот раздаточный материал является дополнительным обсуждением, ведущим к определению измерения и некоторых из его основных свойств.Пусть V — векторное пространство над полем

Дополнительная информация

2.1 Классы сложности

15-859 (M): Рандомизированные алгоритмы Лектор: Шучи Чавла Тема: Классы сложности, проверка личности Дата: 15 сентября 2004 г. Писец: Эндрю Гилпин 2.1 Классы сложности В этой лекции мы рассмотрим

Дополнительная информация

Рандомизированные алгоритмы

Рандомизированные алгоритмы 10 марта 2005 г. 1 Что такое рандомизированные алгоритмы? Алгоритмы, которые используют случайные числа для принятия решений во время выполнения алгоритма.Зачем нам это нужно ?? Детерминированный

Дополнительная информация .

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *