Какое минимальное число бит
Перейти к содержимому

Какое минимальное число бит

  • автор:

Почему для кодирования одного символа нужен именно 1 байт?

Почему для кодирования 1-го символа нужен именно 1 байт? Я прекрасно понимаю, что минимальная единица информации — 1 бит и чтобы выразить 255 символов в двоичном коде надо использовать 8 бит. И по таблице брать двоичный код и по нему находить нужный символ, но почему каждый символ обязательно занимает 1 байт? Зачем записывать число именно вот так 0000001 , а не просто 1 , тем самым заняв всего 1 бит информации и по таблице взять ему соответствующий символ.

Отслеживать
51.6k 204 204 золотых знака 67 67 серебряных знаков 251 251 бронзовый знак
задан 1 авг 2018 в 17:23
Никита Антонов Никита Антонов
125 1 1 серебряный знак 9 9 бронзовых знаков

Байт — минимальная адресуемая единица информации. Хранить каждый символ меньше чем в одном байте неэффективно по скорости доступа. А для длительного хранения (при сохранении в файл, например) никто не мешает применить сжатие.

1 авг 2018 в 17:27
@insolor, Use the answer form, Luke!
– user207618
1 авг 2018 в 17:34
Символы не хранят в одном байте уже лет тридцать 🙂
1 авг 2018 в 17:36

А вообще теоретически использовать один бит не разрешает, только вот 11111111 — это один символ (число 255) или восемь символов 1 ? Придётся добавлять дополнительную информацию, поясняющую, как правильно интерпретировать эти единицы. Ну и да, использовать число битов меньшее чем «минимальная адресуемая единица информации» банально неудобно, ибо именно под восьмибитный байт спроектированы все современные компьютеры

1 авг 2018 в 17:39

@andreymal, о спасибо большое! Теперь дошло! Только вот еще вопрос тоесть большие последовательности в зависимости от кодировки делятся на определенное количество байт (1, 2 и тд) и уже по таблице находится определенные символы ?

1 авг 2018 в 17:42

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Не обязательно 1 ..есть кодировки (например utf-16, utf-32 ) где символы по 2 , по 4 байта. тут еще многое зависит от количества кодируемых символов. не всегда хватает 256 вариантов. часто нужно больше.то есть битность напрямую зависит от числа символов в таблице символов. Если влезть в ассемблер, то можно сделать свою таблицу символов. проблема будет только в том что твою кодировку будет понимать только твоя программа. А так просто принятый стандарт, и все. по поводу же адресации, да — опять же стандарт. хотя есть системы , которые работают и 9-ю битами ( старые советские системы связи) , где 9-й бит был или контрольным или знак передавал.

Отслеживать
ответ дан 1 авг 2018 в 17:35
Сергей Петрашко Сергей Петрашко
1,493 8 8 серебряных знаков 15 15 бронзовых знаков

Я наверное неправильно задал вопрос имею в виду почему все символы имеют 1 и тот же размер(тоесть 2 байта или 1), а не так чтобы 1 символ весит больше, а другой меньше, если все равно старшие разряды заполнены нулями (00000001 к примеру)

1 авг 2018 в 17:38

@НикитаАнтонов в кодировке UTF-8 длина одного символа может быть 1, 2, 3 или 4 байта 🙂 А использовать число бит, не кратное восьми, неудобно из-за архитектуры современных компьютеров, заточенных именно на 8 бит

1 авг 2018 в 17:40

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

Сколько бит занимает число

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

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

Сколько бит в большом целом

Большое целое
Рассчитать
Двоичное представление
Восьмеричных разрядов
Восьмеричное представление
Десятичных разрядов
Десятичное представление
Шестнадцатеричных разрядов
Шестнадцатеричный код
Число байт
Ссылка Сохранить Виджет

Ограничения на длину числа нет — максимум зависит только от ресурсов вашего компьютера.
К примеру, число с одной тысячей нулей можно ввести вот так: 123E1000

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

Битовое представление чисел

Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 ( char ), 16 ( short ), 32 ( int ) или 64 ( long long ) бит.

#Эндианность

Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:

  • При схеме little-endian сначала идут младшие биты. Например, число $42_$ будет храниться так: $010101$.
  • При записи в формате big-endian сначала идут старшие биты. Все примеры из начала статьи даны в big-endian формате.

Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.

Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.

#Битовые операции

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

#Сдвиги

Битовую запись числа можно «сдвигать» влево ( x > y ), что эквивалентно умножению или делению на степень двойки с округлением вниз.

Обычное умножение и деление — не самые быстрые операции, однако все битовые сдвиги всегда работают ровно за один такт. Как следствие, умножение и деление на какую-то фиксированную степень двойки всегда работает быстро — даже если вы не используете сдвиги явно, компилятор скорее всего будет проводить подобную оптимизацию.

#Побитовые операции

Помимо && , || и ! , существуют их побитовые версии, которые применяют соответствующую логическую операцию к целым последовательностям битов: & , | , ~ .

Также помимо них есть ещё операция исключающего «или» (XOR), которая записывается как ^ .

  • $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
  • $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
  • $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$

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

#Маски

Бинарные последовательности можно поставить в соответствие подмножествам какого-то фиксированного множества: если на $i$-той позиции стоит единица, то значит $i$-тый элемент входит множество, а иначе не входит.

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

#Выделить i-й бит числа

Это часто используется для проверки, принадлежит ли $i$-тый элемент множеству:

Напомним, что нумерация идет с младших бит и начинается с нуля.

#Получить число, состоящее из k единиц

#Инвертировать все биты числа

#Добавить i-й элемент в множество

#Удалить $i$-й элемент из множества

#Удалить i-й элемент из множества, если он есть

Также добавляет этот элемент, если его нет.

#Знаковые числа

Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).

Если сложить две unsigned int переменные, сумма которых превосходит $2^$, произойдет переполнение: сумму нельзя будет представить точно, и поэтому вместо неё результатом будут только нижние 32 бит. Все операции с беззнаковыми числами как бы проходят по модулю какой-то степени двойки.

Знаковые же типы нужны для хранения значений, которые могут быть и отрицательными. Для этого нужно выделить один бит для хранение знака — отрицательное ли число или нет — немного пожертвовав верхней границей представимых чисел: теперь самое большое представимое число это $2^-1$, а не $2^-1$.

Инженеры, которые работают над процессорами, ещё более ленивые, чем программисты — это мотивировано не только стремлением к упрощению, но и экономией транзисторов. Поэтому когда в signed типах происходит переполнение, результат в битовом представлении считается так же, как и в случае с unsigned числами. Если мы хотим ничего не менять в плане того, как работают unsigned числа, представление отрицательных чисел должно быть таким, что число $-x$ как бы вычитается из большой степени двойки:

  • Все неотрицательные числа записываются в точности как раньше.
  • У всех отрицательных чисел самый большой бит будет единичным.
  • Если прибавить к $2^-1$ единицу, то результатом будет $-2^$, представляемое как 10000000 (в целях изложения мы будем записывать 8 бит, хотя в int их 32).
  • Зная двоичную запись положительного числа x , запись -x можно получить как ~x + 1 .
  • -1 записывается как ~1 + 1 = 11111110 + 00000001 = 11111111 .
  • -42 записывается как ~42 + 1 = 11010101 + 00000001 = 11010110 .
  • После -1 = 11111111 идет 0 = -1 + 1 = 11111111 + 00000001 = 00000000 .

Упражнение. Каких чисел больше: положительных или отрицательных?

Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.

#128-битные числа

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

Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.

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

как подсчитать минимальное количество битов требуемое для десятичных чисел в бинарном коде?

Для целых чисел без знака: взять логарифм по основанию 2 и округлить в большую сторону.

log2271 = 8.082 -> 9 бит

log2521 = 9.025 -> 10 бит

Для представления нуля в памяти всё равно требуется хотя бы 1 бит

Отслеживать
ответ дан 12 сен 2015 в 4:29
5,733 13 13 серебряных знаков 31 31 бронзовый знак
а почему,в первый раз вы добивили 1 к 270 а 520 не добавили?
12 сен 2015 в 4:52
@Павел опечатался
12 сен 2015 в 4:56

В общем случае логарифм от количества различных чисел, которые мы хотим представить. Например, для чисел от -128 до 127 это log_2(256) = 8

12 сен 2015 в 5:30

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

12 сен 2015 в 10:47

@NickVolynkin: Ну, если нам понадобится, к примеру, закодировать значения от 200 до 203, то вполне возможно использовать два бита: 200 → 00, 201 → 01, 202 → 10, 203 → 11.

12 сен 2015 в 11:24

Если уж говорить о скорости, то некоторые архитектуры (в т.ч. x86) имеют инструкцию, которая считает количество лидирующих нулевых бит. Компилятор GCC имеет её встроенный аналог (обёртку).

#include int main() < std::cout 

Отслеживать
ответ дан 12 сен 2015 в 11:02
Антон Сазонов Антон Сазонов
713 3 3 серебряных знака 12 12 бронзовых знаков

Делим на 2, пока получается число большее единицы, считаем итерации, к результату добавляем 1. Добавляем ещё 1, если число отрицательное.

Отслеживать
ответ дан 12 сен 2015 в 4:27
11111000000 11111000000
3,599 12 12 серебряных знаков 25 25 бронзовых знаков

Предварительно генерируем массив степеней двойки. Cравниваем число со степенями из массива, пока не найдём первое превышающее. Индекс этого числа и есть искомый размер.

Вот код и тесты:

import org.junit.Assert; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import java.util.Arrays; import java.util.Collection; @RunWith(Parameterized.class) public class Algorithms < public static int[] powersOfTwo = new int[31]; static < powersOfTwo[0] = 1; for (int power = 1; power < powersOfTwo.length; power++) < powersOfTwo[power] = powersOfTwo[power - 1] * 2; >> @Parameterized.Parameter(0) public int number; @Parameterized.Parameter(1) public int size; @Parameterized.Parameters(name = "number:, size:") public static Collection data() < return Arrays.asList(new Object[][]< , , , <((int) Math.pow(2, 10)) - 1, 10>, <((int) Math.pow(2, 10)), 10>, <((int) Math.pow(2, 10)) + 1, 11>, >); > public static int getSizeOf(int number) < for (int power = 1; power < 30; power++) < if (powersOfTwo[power] >= number) return power; > return 31; > @Test public void testSizeOf() < Assert.assertEquals(size, getSizeOf(number)); >> 

Этот алгоритм должен быть быстрее, чем вычисление логарифмов или деление.

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

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