Знайте, когда есть одинаковое количество 1 и 0 на одну строку

Question

Интересует использование побитовых операторов для подсчета числа 1 с = 0 в битовой строке.Если 1с = 0с, выведите.Любые идеи по использованию Java для достижения этой цели?Спасибо.

public void function(int binaryNumber) {
    BigInteger val = new BigInteger(String.valueOf(binaryNumber));
    val = val.abs();
    int count = val.bitCount();
    String binaryString = val.toString(2);

    System.out.println("count = " + count);
    System.out.println("bin = " + binaryString);
}

Answer 1

Непонятно, что вы имели в виду под "Битовой строкой", но я предполагаю, что это может означать двоичную последовательность любой длины.В исходном коде вы используете объект BigInteger, который не поддерживает примитивные побитовые операторы, такие как |, &&, ^.

Однако ваша реализация поддерживает только целочисленные значения с максимальным значением около двух миллиардов или 31двоичные цифры, так как целые имеют 32 бита, а начальный бит является знаковым битом, который не используется в вашем вопросе.Вместо этого просто позвольте функции передать переменную String и val = new BigInteger(val).

Из вашего binaryString, который является строкой, являющейся вашим двоичным представлением вашего BigInteger, вы можете просто выполнить циклсимволы и отслеживать единицы и нули.Просто добавьте этот код после System.out.println("bin = " + binaryString);:

int zeroes = 0;
int ones = 0;
for (int k = 0; k < binaryString.length(); k++) {
    if (binaryString.charAt(k) == '0')
        zeroes++;
    if (binaryString.charAt(k) == '1')
        ones++;
}

Однако, если вы хотите использовать «битовые операторы» для BigIntegers, используйте битовую маску и shift методы, чтобы определить, содержит ли он единицу или ноль.Для версии BigInteger рассмотрите возможность использования этого кода после System.out.println("bin = " + binaryString);:

int zeroes = 0;
int ones = 0;
int bitindex = 0;
BigInteger bitmask = new BigInteger(String.valueOf("1"));
// BigInteger supports bitLength().
while (bitindex <= val.bitLength()) {
    // Bit mask has all but one bit equal zero. The AND operation cancels all
    // the bits except the one bit equal to one.
    if (bitmask.and(val).equals(BigInteger.ZERO))
        zeroes++;
    else
        ones++;

    bitindex++;
    bitmask = bitmask.shiftLeft(1);
}

Это можно сделать аналогично для версии int (или long), учитывая, что все конечные нули отбрасываются:

int zeroes = 0;
int ones = 0;

long bitmask = 1;
// Loop stops once the one bit gone above the most significant one bit one the val
// because from that point the bitmask will always be greater than val
while (bitmask >= 0 && bitmask <= val) {
    if ((bitmask & val) == 0)
        zeroes++;
    else
        ones++;
    bitmask <<= 1; // Operator << means left shift
}

Answer 2

Обновление: Отображение формата битов без знака, добавленные версии long и BigInteger и добавленные версии без знака.

Класс Integerимеет много static методов для создания бит магии.Не нужно использовать BigInteger, если ввод int.Long имеет те же методы, если это необходимо.

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

• bitCount(int i) - Возвращает число однобитных в двоичном представлении дополнения двух указанного intзначение.

• numberOfLeadingZeros(int i) - Возвращает число нулевых битов, предшествующих однобитному старшему («крайнему левому») разряду inдвоичное представление дополнения до двух указанных значений int.Возвращает 32, если указанное значение не имеет однобитовых значений в представлении дополнения до двух, другими словами, если оно равно нулю.

• SIZE -число битов, используемых для представления значения типа int в двоичной форме дополнения до двух (мы все знаем, что это 32) .

Поскольку мы хотим игнорировать ведущие нули, SIZE - numberOfLeadingZeros сообщит нам фактическое количество использованных битов.

public static boolean oneBitsEqualsZeroBits(int value) {
    if (value == 0)
        return false;
    int bitsUsed = Integer.SIZE - Integer.numberOfLeadingZeros(value);
    int oneBits = Integer.bitCount(value);
    int zeroBits = bitsUsed - oneBits;
    return (oneBits == zeroBits);
}

Оно может быть сокращено, хотя и немного неясно, но объяснимо.Предположим, 0s == 1s, поэтому bitCount - это число 1s + bitCount - это число 0s, т.е. bitCount * 2 - это количество используемых битов.Добавьте число лидирующих нулей и все биты int должны быть учтены.

public static boolean oneBitsEqualsZeroBits(int value) {
    return (value != 0 && Integer.numberOfLeadingZeros(value) + 2 * Integer.bitCount(value) == 32);
}

То же самое для long версии:

public static boolean oneBitsEqualsZeroBits(long value) {
    return (value != 0 && Long.numberOfLeadingZeros(value) + 2 * Long.bitCount(value) == 64);
}

Для BigInteger, считая старшиенули не имеют смысла, так как без фиксированной битовой ширины нет ведущих нулей.Вместо этого у нас есть другой метод:

• bitLength(): Возвращает количество бит в минимальном представлении с двумя дополнительными символами этого BigInteger, исключая знаковый бит.

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

public static boolean oneBitsEqualsZeroBits(BigInteger value) {
    if (value.signum() == 0)
        return false;
    if (value.signum() > 0)
        return (2 * value.bitCount() == value.bitLength());
    return (2 * value.bitCount() == value.bitLength() + 1);
}

3 версиибудет обрабатывать отрицательные значения по-разному, поскольку int и long будут выполнять расширение знака до 32 и 64 бит соответственно.

Тест (только для версии int)

public static void main(String[] args) {
    test(0, false);
    test(1, false);
    test(0b10, true);
    test(0b11, false);
    test(0b100, false);
    test(0b1000, false);
    test(0b1001, true);
    test(0b1010, true);
    test(0b1011, false);
    test(0b1100, true);
    test(0b1101, false);
    test(0b101010_11110000_00111100_00001111, true);
    test(0b11001100_01010101_01100110_11100010, true);
    test(0b11111111_11111111_11111111_11111111, false);
}

public static void test(int value, boolean expected) {
    boolean result = oneBitsEqualsZeroBits(value);
    System.out.printf("%11d %8x %-5s %3s %s%n", value, value, result,
                      (result == expected ? "OK" : "ERR"),
                      Integer.toUnsignedString(value, 2));
}

Вывод (заголовок добавлен вручную для ответа)

    Decimal      Hex Result    Binary
          0        0 false  OK 0
          1        1 false  OK 1
          2        2 true   OK 10
          3        3 false  OK 11
          4        4 false  OK 100
          8        8 false  OK 1000
          9        9 true   OK 1001
         10        a true   OK 1010
         11        b false  OK 1011
         12        c true   OK 1100
         13        d false  OK 1101
  720387087 2af03c0f true   OK 101010111100000011110000001111
 -866818334 cc5566e2 true   OK 11001100010101010110011011100010
         -1 ffffffff false  OK 11111111111111111111111111111111

Игнорирующий знак

Если вы хотите сравнить 1си 0 на строковом представлении числа, игнорируя знак, т.е. на abs(value), затем вы меняете методы для применения abs():

public static boolean oneBitsEqualsZeroBits(int value) {
    if (value == 0 || value == Integer.MIN_VALUE)
        return false;
    if (value < 0)
        value = -value;
    return (Integer.numberOfLeadingZeros(value) + 2 * Integer.bitCount(value) == 32);
}

public static boolean oneBitsEqualsZeroBits(long value) {
    if (value == 0 || value == Long.MIN_VALUE)
        return false;
    if (value < 0)
        value = -value;
    return (Long.numberOfLeadingZeros(value) + 2 * Long.bitCount(value) == 64);
}

public static boolean oneBitsEqualsZeroBits(BigInteger value) {
    value = value.abs();
    return (value.signum() != 0 && 2 * value.bitCount() == value.bitLength());
}