C обратные биты в целом числе без знака

Question

Я преобразую целое число без знака в двоичное, используя побитовые операторы, и в настоящее время делаю целое число & 1, чтобы проверить, равен ли бит 1 или 0, и выводит, затем сдвиг вправо на 1 для деления на 2. Однако биты возвращаютсянеправильный порядок (обратный), поэтому я решил поменять порядок бит в целых числах перед началом.

Есть ли простой способ сделать это?

Пример: Итак, если мне дано целое число без знака 10 = 1010

while (x not eq 0) 
  if (x & 1)
    output a '1'
  else 
    output a '0'
  right shift x by 1

, это возвращает 0101, что неверно... так что я думал поменять порядок битов изначально до запуска цикла, но я не уверен, как это сделать?

Answer 1

Обращать биты в слове раздражает, и проще просто выводить их в обратном порядке. Например.,

void write_u32(uint32_t x)
{
    int i;
    for (i = 0; i < 32; ++i)
        putchar((x & ((uint32_t) 1 << (31 - i)) ? '1' : '0');
}

Вот типичное решение для изменения порядка битов:

uint32_t reverse(uint32_t x)
{
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
    x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16);
    return x;
}

Answer 2

Вы можете просто пройтись по битам от большого конца к маленькому концу.

#define N_BITS (sizeof(unsigned) * CHAR_BIT)
#define HI_BIT (1 << (N_BITS - 1))

for (int i = 0; i < N_BITS; i++) {
     printf("%d", !!(x & HI_BIT));
     x <<= 1;
}

Где !! также может быть написано !=0 или >> (N_BITS - 1).

Answer 3

вместо этого вы можете перемещаться слева направо, то есть сдвигать единицу от MSB к LSB, например:

unsigned n = 20543;
unsigned x = 1<<31;
while (x) {
    printf("%u ", (x&n)!=0);
    x = x>>1;
}

Answer 4

Лучший способ обратить бит в целое число:

1. Это очень эффективно.
2. Он работает только тогда, когда крайний левый бит равен 1.

КОД SNIPPET

int reverse ( unsigned int n )
{
    int x = 0;
    int mask = 1;
    while ( n > 0 )
    {
        x = x << 1;
        if ( mask & n )
            x = x | 1;
        n = n >> 1;
    }
    return x;
}

Answer 5

unsigned int rev_bits(unsigned int input)
{
    unsigned int output = 0;
    unsigned int n = sizeof(input) << 3;
    unsigned int i = 0;

    for (i = 0; i < n; i++)
        if ((input >> i) & 0x1)
            output |=  (0x1 << (n - 1 - i));

    return output;
}

Answer 6

Вы можете обратить биты так, как вы выводите их, и вместо этого сохранить их в другом целом числе, и сделать это снова:

for (i = 0; i < (sizeof(unsigned int) * CHAR_BIT); i++)
{
  new_int |= (original_int & 1);
  original_int = original_int >> 1;
  new_int = new_int << 1;
}

Или вы можете просто сделать наоборот, сдвинув маску:

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while (mask > 0)
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
}

Если вы хотите удалить начальные 0, вы можете подождать, пока напечатается 1, или выполнить предварительный просмотр:

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while ((mask > 0) && ((original_int & mask) == 0))
  mask = mask >> 1;
do
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
} while (mask > 0);

таким образом вы поместите маску на первую напечатанную 1 и забудете о первых 0

Но помните: вывести двоичное значение целого числа можно только с помощью printf

Answer 7

Второй ответ Дитриха Эппа, вероятно, лучший на современном процессоре с высокоскоростными кэшами.Однако на типичных микроконтроллерах это не так, и следующее не только намного быстрее, но и более универсально и более компактно (в C):

// reverse a byte
uint8_t reverse_u8(uint8_t x)
{
   const unsigned char * rev = "\x0\x8\x4\xC\x2\xA\x6\xE\x1\x9\x5\xD\x3\xB\x7\xF";
   return rev[(x & 0xF0) >> 4] | (rev[x & 0x0F] << 4);
}

// reverse a word
uint16_t reverse_u16(uint16_t x)
{
   return reverse_u8(x >> 8) | (reverse_u8(x & 0xFF) << 8);
}

// reverse a long
uint32_t reverse_u32(uint32_t x)
{
   return reverse_u16(x >> 16) | (reverse_u16(x & 0xFFFF) << 16);
}

Код легко переводится на Java, Go, Rustи т.д. Конечно, если вам нужно только напечатать цифры, лучше всего печатать в обратном порядке (см. ответ Дитриха Эппа).

Answer 8

Я полагаю, что вопрос состоит в том, как не выводить в обратном порядке.

Забавный ответ (рекурсия):

#include <stdio.h>

void print_bits_r(unsigned int x){
    if(x==0){
       printf("0");
       return;
    }
    unsigned int n=x>>1;
    if(n!=0){
       print_bits_r(n);
    }
    if(x&1){
        printf("1");
    }else{
        printf("0");
    }
}


void print_bits(unsigned int x){
    printf("%u=",x);
    print_bits_r(x);
    printf("\n");
}

int main(void) {
    print_bits(10u);//1010
    print_bits((1<<5)+(1<<4)+1);//110001
    print_bits(498598u);//1111001101110100110
    return 0;
}

Ожидаемый вывод:

10=1010
49=110001
498598=1111001101110100110

Последовательная версия (сначала отбирает старшие биты):

#include <limits.h>//Defines CHAR_BIT
//....
void print_bits_r(unsigned int x){
    //unsigned int mask=(UINT_MAX>>1)+1u;//Also works...
    unsigned int mask=1u<<(CHAR_BIT*sizeof(unsigned int)-1u);
    int start=0;
    while(mask!=0){
        if((x&mask)!=0){
            printf("1");
            start=1;
        }else{
            if(start){
                printf("0");
            }
        }
        mask>>=1;
    }
    if(!start){
       printf("0");
    }    
}

Answer 9

Вы можете изменить unsigned 32-bit integer и вернуться с помощью следующей функции reverse:

unsigned int reverse(unsigned int A) {
    unsigned int B = 0;
    for(int i=0;i<32;i++){
        unsigned int j = pow(2,31-i);
        if((A & (1<<i)) == (1<<i)) B += j; 
    }
return B; 
}

Не забудьте включить библиотеку математики.Удачного кодирования:)

Answer 10

Вот версия golang обратных битов в целых числах, если кто-то ищет их. Я написал это с подходом, аналогичным обращению строки в c. Переходя от битов 0 к 15 (31/2), меняйте бит i на бит (31-i) Пожалуйста, проверьте следующий код.

package main
import "fmt"

func main() {
    var num = 2
    //swap bits at index i and 31-i for i between 0-15
    for i := 0; i < 31/2; i++ {
        swap(&num, uint(i))
    }
    fmt.Printf("num is %d", num)
}

//check if bit at index is set
func isSet(num *int, index uint) int {
    return *num & (1 << index)
}

//set bit at index
func set(num *int, index uint) {
    *num = *num | (1 << index)
}

//reset bit at index
func reSet(num *int, index uint) {
    *num = *num & ^(1 << index)
}

//swap bits on index and 31-index
func swap(num *int, index uint) {
    //check index and 31-index bits
    a := isSet(num, index)
    b := isSet(num, uint(31)-index)
    if a != 0 {
        //bit at index is 1, set 31-index
        set(num, uint(31)-index)
    } else {
        //bit at index is 0, reset 31-index
        reSet(num, uint(31)-index)
    }
    if b != 0 {
        set(num, index)
    } else {
        reSet(num, index)
    }
}`