Лучший способ перебрать битовые векторы как массивы в C - PullRequest
Новая
       79

Лучший способ перебрать битовые векторы как массивы в C

0 голосов
/ 07 января 2019

Раньше, когда я перебирал битовые векторы, я использовал такие строки, как "0001", "0010", "0011" и т. Д. Я бы анализировал целые 10 чисел в строковые представления с правильной базой, используя Java, однако я быстро закончилась память.

Используя C, я ищу способ перебирать битовые векторы заданной длины. Если длина 4, я бы вызвал массив int [4] и использовал бы цикл for, чтобы заполнить каждую позицию нулями для начала. Моя проблема начинается с того, что мне нужно добавить числа, переходя от [0,0,0,0] к [0,0,1,0] и т. Д. И т. П. До состояния [1,1,1,1] ] встречается.

Я попробовал этот код ниже. 

int array[4];
for (i=0; i<4; i++)
{
  array[i] = 0;
}
for (i=0; i<4; i++)
{
  for(x=0; x<4; x++)
   {
     if (array[4-x] == 0 && (4-x) != 1)
      {
        array = array;
      }
     if (array[4-x] == 1)
      {
        array[4-x] == 0;
        array[4-x +1] ==1;
      }
   }
}

но это не правильно. Любая помощь будет оценена.

1 Ответ

0 голосов
/ 07 января 2019

Я бы использовал uint64_t из <inttypes.h> (который включает <stdint.h>, где они на самом деле определены), до 64 бит.

Если мы пронумеровали биты от 0 до 63, где 0 - младший значащий бит, то бит i соответствует числовому значению 2 i . (2 0 = 1, 2 1 = 2, 2 2 = 4, 2 3 = 8, 2 4 = 16 и т. Д.)

Чтобы проверить, установлен ли определенный бит (ненулевой) или очищен (ноль), мы можем использовать 

static inline int  bit_is_set(const uint64_t  value, const int  bit)
{
    return !!(value & (((uint64_t)1) << bit));
}

static inline int  bit_is_clear(const uint64_t  value, const int  bit)
{
    return !(value & (((uint64_t)1) << bit));
}

Выше приведено значение True (1), если бит установлен / сброшен, и False (0) в противном случае.

(! - оператор Not, логическая инверсия. !! - оператор Not-Not. Если x - арифметическое выражение или числовое значение, !!x равно 0, если x равно 0, и 1, если x отличен от нуля. Это выглядит забавно, но помните, оно просто держит ноль ноль и преобразует ненулевое значение в 1. Довольно полезно.)

Чтобы изменить отдельный бит, мы можем использовать 

static inline uint64_t  set_bit(const uint64_t  value, const int  bit)
{
    return value | (((uint64_t)1) << bit);
}

static inline uint64_t  clear_bit(const uint64_t  value, const int  bit)
{
    return value & (~(((uint64_t)1) << bit));
}

static inline uint64_t  flip_bit(const uint64_t  value, const int  bit)
{
    return value ^ (((uint64_t)1) << bit);
}

В C параметры передаются по значению, поэтому сам параметр не изменяется: функции возвращают значение с заданным битом, установленным / очищенным / перевернутым (измененным).

Вы можете использовать 

    printf("value is now %" PRIu64 ".\n", value);

для печати uint64_t value;.

Для разбора параметров командной строки на uint64_t с я использую что-то вроде 

#include <stdlib.h>
#include <inttypes.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    uint64_t  a, b;
    char      dummy;

    if (argc != 3) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
        fprintf(stderr, "       %s A B\n", argv[0]);
        fprintf(stderr, "\n");
        fprintf(stderr, "This program calculates the binary OR of A and B.\n");
        fprintf(stderr, "\n");
        return EXIT_FAILURE;
    }

    if (sscanf(argv[1], " %" SCNu64 " %c", &a, &dummy) != 1) {
        fprintf(stderr, "%s: Not a 64-bit unsigned integer.\n", argv[1]);
        return EXIT_FAILURE;
    }

    if (sscanf(argv[2], " %" SCNu64 " %c", &b, &dummy) != 1) {
        fprintf(stderr, "%s: Not a 64-bit unsigned integer.\n", argv[2]);
        return EXIT_FAILURE;
    }

    printf("A = %" PRIu64 "\n", a);
    printf("B = %" PRIu64 "\n", b);
    printf("A | B = %" PRIu64 "\n", a | b);

    return EXIT_SUCCESS;
}

Обратите внимание, что семейство функций scanf () не выдает ошибку при переполнении. Это означает, что если вы введете 11111111111111111111111111111111, это будет показано как-то еще, обычно 18446744073709551615 (= UINT64_MAX).

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

...