Общие представления о языке Java 5 (стр. 26 из 68)

Как уже говорилось, умножение двоичных чисел осуществляется путем сложений и сдвигов по алгоритму, напоминающему умножение “в столбик”, но гораздо более простому, так как умножить надо только на 0 или 1. При целочисленном умножении выход за пределы разрядности ячейки происходит гораздо чаще, чем при сложении или вычитании. Например, 110₂

101₂=110₂ 100₂+110₂ 1₂=11000₂+110₂=11100₂. Если наша ячейка четырехразрядная, произойдет выход за ее пределы, и мы получим после отбрасывания лишнего бита 1110₂= -2₁₀<0. Таким образом, умножение целых чисел легко может дать неправильный результат. В том числе – даже отрицательное число. Поэтому при работе с целочисленными типами данных следует обращать особое внимание на то, чтобы в программе не возникало ситуаций арифметического переполнения. Повышение разрядности целочисленных переменных позволяет смягчить проблему, хотя полностью её не устраняет. Например, зададим переменные

byte m=10,n=10,k=10;

Тогда значения m*n, m*k и n*k будут лежать в разрешённом диапазоне

-128..127. А вот m*n + m*k из него выйдет. Не говоря уж об m*n*k.

Если мы зададим

int m=10,n=10,k=10;

переполнения не возникнет даже для m*n*k. Однако, при m=n=k=100 значение m*n*k будет равно 10⁶, что заметно выходит за пределы разрешённого диапазона –32768..32767. Хотя m*n, m*k и n*k не будут за него выходить (но уже 4*m*n за него выйдет). Использование типа long поможет и в этом случае. Однако уже значения m=n=k=2000 (не такие уж большие!) опять приведут к выходу m*n*k за пределы диапазона. Хотя для m*n выход произойдёт только при значениях около 50000.

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

Пример:

byte i=127, j=1, k;

k=(byte)(i+j);

System.out.println(k);

В результате получим число (-128). Если бы мы попробовали написать

byte i=127,j=1,k;

System.out.println(i+j);

то получили бы +128. Напомним, что значения величин типа byte перед проведением сложения преобразуются в значения типа int.

Шестнадцатеричное представление целых чисел и перевод из одной системы счисления в другую

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

. В десятичной системе счисления имеется только 10 цифр: 0,1,2,3,4,5,6,7,8,9. А в 16-ричной системе счисления должно быть 16 цифр. Принято обозначать недостающие цифры заглавными буквами латинского алфавита: A,B,C,D,E,F. То есть

, , , , , . Таким образом, к примеру, .

В Java для того, чтобы отличать 16-ричные числа, как мы уже знаем, перед ними ставят префикс 0x: 0xFF обозначает

, а 0x10 – это 10₁₆, то есть 16.

Число N может быть записано с помощью разных систем счисления. Например, в десятичной:

N = A_n 10ⁿ + ... + A₂ 10² + A₁ 10¹ + A₀ 10⁰ ( A_n = 0 .. 9)

или в двоичной:

N = B_n 2ⁿ + ... + B₂ 2² + B₁ 2¹ + B₀ 2⁰ ( B_n = 0 или 1 )

или в шестнадцатеричной:

N = C_n 16ⁿ + ... + C₂ 16² + C₁ 16¹ + C₀ 16⁰ ( C_n = 0 .. F )

Преобразование в другую систему счисления сводится к нахождению соответствующих коэффициентов. Например, B_n по известным коэффициентам A_n – при переводе из десятичной системы в двоичную, или коэффициентов A_n по коэффициентам B_n - из двоичной системы в десятичную.

Преобразование чисел из системы с меньшим основанием в систему с большим основанием

Рассмотрим преобразование из двоичной системы в десятичную. Запишем число N в виде

N = B_n 2ⁿ + ... + B₂ 2² + B₁ 2¹ + B₀ 2⁰ ( B_n = 0 или 1 )

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

Пример:

Преобразуем 01011110₂ к десятичному виду. Имеем:

01011110₂ = 0×2⁷+1×2⁶+0×2⁵+1×2⁴+1×2³+1×2²+1×2¹+0×2⁰=

= 0 + 64 + 0 + 16 + 8 + 4 + 2 + 0 =

= 94₁₀

Преобразование чисел из системы с большим основанием в систему с меньшим основанием

Рассмотрим его на примере преобразования из десятичной системы в двоичную. Нужно для известного числа N₁₀ найти коэффициенты в выражении

N = B_n 2ⁿ + ... + B₂ 2² + B₁ 2¹ + B₀ 2⁰ ( B_n = 0 или 1 )

Воспользуемся следующим алгоритмом: в десятичной системе разделим число N на 2 с остатком. Остаток деления (он не превосходит делителя) даст коэффициент B₀ при младшей степени 2⁰. Далее делим на 2 частное, полученное от предыдущего деления. Остаток деления будет следующим коэффициентом B₁ двоичной записи N. Повторяя эту процедуру до тех пор, пока частное не станет равным нулю, получим последовательность коэффициентов B_n.

Например, преобразуем 345₁₀ к двоичному виду. Имеем:

частное остаток B_i

345 / 2 172 1 B₀

172 / 2 86 0 B₁

86 / 2 43 0 B₂

43 / 2 21 1 B₃

21 / 2 10 1 B₄

10 / 2 5 0 B₅

5 / 2 2 1 B₆

2 / 2 1 0 B₇

1 / 2 0 1 B₈

345₁₀ = 101011001₂

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

Рассмотрим число N в двоичном и шестнадцатеричном представлениях.

N = B_n 2ⁿ + ... + B₂ 2² + B₁ 2¹ + B₀ 2⁰ ( B_i = 0 или 1 )

N = H_n 16ⁿ + ... + H₂ 16² + H₁ 16¹ + H₀ 16⁰ ( H_i = 0 .. F₁₆ , где F₁₆ =15₁₀)

Заметим, что 16 = 2⁴. Объединим цифры в двоичной записи числа группами по четыре. Каждая группа из четырех двоичных цифр представляет число от 0 до F₁₆ , то есть от 0 до15₁₀. От группы к группе вес цифры изменяется в 2⁴=16 раз (основание 16-ричной системы). Таким образом, перевод чисел из двоичного представления в шестнадцатеричное и обратно осуществляется простой заменой всех групп из четырех двоичных цифр на шестнадцатеричные (по одному на каждую группу) и обратно :

0000₂ = 0₁₆

0001₂ = 1₁₆

0010₂ = 2₁₆

0011₂ = 3₁₆

0100₂ = 4₁₆

0101₂ = 5₁₆

0110₂ = 6₁₆

0111₂ = 7₁₆

1000₂ = 8₁₆

1001₂ = 9₁₆

1010₂ = A₁₆

1011₂ = B₁₆

1100₂ = C₁₆

1101₂ = D₁₆

1110₂ = E₁₆

1111₂ = F₁₆

Например, преобразуем 1011010111₂ к шестнадцатеричному виду:

1011010111₂ = 0010 1101 0111₂ = 2D7₁₆

4.2. Побитовые маски и сдвиги

Оператор	Название	Пример	Примечание
~	Оператор побитового дополнения (побитовое “не”, побитовое отрицание)	~i
^	Оператор “ побитовое исключающее или” (XOR)	i^j
&	Оператор “побитовое и” (AND)	i&j
|	Оператор “побитовое или” (OR)	i|j

<<	Оператор левого побитового сдвига
>>>	Оператор беззнакового правого побитового сдвига
>>	Оператор правого побитового сдвига с сохранением знака отрицательного числа

&=	y&=x эквивалентно y=y&x
|=	y|=x эквивалентно y=y|x
^=	y^=x эквивалентно y=y^x
>>=	y>>=x эквивалентно y= y>>x
>>>=	y>>>=x эквивалентно y= y>>>x
<<=	y<<=x эквивалентно y= y<<x

Побитовые операции – когда целые числа рассматриваются как наборы бит, где 0 и 1 играют роли логического нуля и логической единицы. При этом все логические операции для двух чисел осуществляются поразрядно – k-тый разряд первого числа с k-тым разрядом второго. Для простоты мы будем рассматривать четырёхбитовые ячейки, хотя реально самая малая по размеру ячейка восьмибитовая и соответствует типу byte.

а) установка в числе a нужных бит в 1 с помощью маски m операцией a|m (арифметический, или, что то же, побитовый оператор OR).