Подсчитать количество единиц в двоичной записи огромного числа

Рейтинг: 0Ответов: 2Опубликовано: 01.05.2023

Задача: Сколько единиц содержится в двоичной записи значения выражения: 4^2020 + 2^2017 – 15?

Так как число превышает допустимое значение типа double, моя программа выводит неправильный ответ: vr = infinity, count = 1. (count должен равняться 2015)

    double vr = Math.Pow(4, 2020) + Math.Pow(2, 2017) - 15; // наше выражение
    string b = Convert.ToString((int)vr, 2);
    int count = 0; //счётчик единиц
    for (int i = 0; i < b.Length; i++)
    {
        if (b[i] == '1')
        {
            count++;
        }
    }
    Console.WriteLine(count);
c# консоль числа системы-счисления
Источник: Stack Overflow на русском

Ответы

▲ 5Принят

@MBo! В двоичной записи числа 4 одна единица (100), и в какую целую степень его не возводи, так одна единица и останется. Например: 4^2=16 (10000). Тоже самое касается и двойки. Сразу преобразуем 4^2020 в 2^4040.

Далее, в двоичной системе. Если к одному числу вида 1 с нулями добавить меньшее такого же вида, то получится 2 единицы, например: 10000+100=10100. Теперь найдём разность большого числа и 15, например: 1000 0000 0000-1111=111 1111 0001, то есть такое вычитание добавляет Z-4 единиц, где Z - степень наименьшей единицы в числе, которая равна степени меньшего числа. Итого ответ равен 2+Z-4=Z-2

Вот и ответ: 2015.

И вправду ошибка была, даже две.

▲ 0

Решение с использованием класса BigInteger:

    BigInteger vr = BigInteger.Pow(4, 2020) + BigInteger.Pow(2, 2017) -15;
    Console.WriteLine(BigInteger.PopCount(vr));