조금 반전의 정수를 무시하고,정수기와 엔디안

StackOverflow https://stackoverflow.com/questions/63776

  •  09-06-2019
  •  | 
  •  

문제

주어진 정수 typedef:

typedef unsigned int TYPE;

나

typedef unsigned long TYPE;

나는 다음과 같은 코드를 반대로 조금의 정수:

TYPE max_bit= (TYPE)-1;

void reverse_int_setup()
{
    TYPE bits= (TYPE)max_bit;

    while (bits <<= 1)
        max_bit= bits;
}

TYPE reverse_int(TYPE arg)
{
    TYPE    bit_setter= 1, bit_tester= max_bit, result= 0;

    for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
        if (arg & bit_tester)
            result|= bit_setter;
    return result;
}

하나는 그냥 요구를 실행하는 최초의 reverse_int_setup()저장하는 정수와 함께 가장 높은 비트 설정에서,어떤 통화를 reverse_int(arg 리) arg 그것의 비트는 반전(을 키로 사용하는 이진 나무,에서 촬영한 증가 카운터,그러나 그것은 더 많거나 적은 무관).

이 있는 플랫폼 독립적 방법에서 컴파일한 시간에 올바른 값을 max_int 를 호출한 후 reverse_int_setup();그렇지 않으면 거기 알고리즘을 고려할 더/날씬하고 보다 중 하나가 대한 reverse_int()?

감사합니다.

도움이 되었습니까?

해결책 

#include<stdio.h>
#include<limits.h>

#define TYPE_BITS sizeof(TYPE)*CHAR_BIT

typedef unsigned long TYPE;

TYPE reverser(TYPE n)
{
    TYPE nrev = 0, i, bit1, bit2;
    int count;

    for(i = 0; i < TYPE_BITS; i += 2)
    {
        /*In each iteration, we  swap one bit on the 'right half' 
        of the number with another on the left half*/

        count = TYPE_BITS - i - 1;  /*this is used to find how many positions 
                                    to the left (and right) we gotta move 
                                    the bits in this iteration*/

        bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
        bit1 <<= count;         /*Shift it to where it belongs*/

        bit2 = n & 1<<((i/2) + count);  /*Find the 'left half' bit*/
        bit2 >>= count;         /*Place that bit in bit1's original position*/

        nrev |= bit1;   /*Now add the bits to the reversal result*/
        nrev |= bit2;
    }
    return nrev;
}

int main()
{
    TYPE n = 6;

    printf("%lu", reverser(n));
    return 0;
}

이번 사용한'비트 수를'아이디어에서 TK 지만,그것을 좀 더 휴대용하지 않고 가정하면 바이트를 포함하는 8 비트와는 대신 사용하여 CHAR_BIT 매크로입니다.코드를 더 효율적으로는 지금(안에 대한 반복을 제거).나는 코드입니다 약간 적은 비밀이다.:)

에 대한 필요를 사용하여 카운트하는 위치의 수에 의해는 우리가 이동하는 비트에 따라 다릅 각 반복-우리는 이동하는 맨 오른쪽 bit31 위치를(가정하면 32 비트 번호)가,두 번째는 오른쪽 bit29 위치 및니다.따라서 계산이 감소해야와 각 반복 내가 증가합니다.

는 희망 정보의 비트는 증명을 이해하는 데 도움이 되는 코드...

다른 팁

다음과 같은 프로그램를 제공하여 적어 알고리즘 반전을 위한 비트는 쉽게 확장할 수 있습을 처리하 64 비트 숫자입니다.

#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
        int32_t x;
        if ( argc != 2 ) 
        {
                printf("Usage: %s hexadecimal\n", argv[0]);
                return 1;
        }

        sscanf(argv[1],"%x", &x);
        /* swap every neigbouring bit */
        x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
        /* swap every 2 neighbouring bits */
        x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
        /* swap every 4 neighbouring bits */
        x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
        /* swap every 8 neighbouring bits */
        x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
        /* and so forth, for say, 32 bit int */
        x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
        printf("0x%x\n",x);
        return 0;
}

이 코드가 포함되어 있지 않아야 합류,그리고 테스트를 사용하여 0x12345678 생산 0x1e6a2c48 는 올바른 대답이다.

typedef unsigned long TYPE;

TYPE reverser(TYPE n)
{
    TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
    int count;

    for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
    {
        /*In each iteration, we  swap one bit 
            on the 'right half' of the number with another 
            on the left half*/

        k = 1<<i; /*this is used to find how many positions 
                    to the left (or right, for the other bit) 
                    we gotta move the bits in this iteration*/

        count = 0;

        while(k << 1 && k << 1 != 1)
        {
            k <<= 1;
            count++;
        }

        nrevbit1 = n & (1<<(i/2));
        nrevbit1 <<= count;

        nrevbit2 = n & 1<<((i/2) + count);
        nrevbit2 >>= count;

        nrev |= nrevbit1;
        nrev |= nrevbit2;
    }
    return nrev;
}

이 정보에 대해서는 gcc 윈도우에서 그러나 나는 확실하지 않다면 그것은 완전히 플랫폼 독립적입니다.몇 곳을 우려의습니다:

  • 조건에 대한 루프로 가정할 때는 왼쪽으로 이동 1 번 왼쪽,당신을 얻을 하 0 1'어'(나는 무엇을 기대하고 무엇이 좋은 오래 된 Turbo C iirc),또는 1 원이 주변에 얻을 1(무엇이 될 것으로 보인 gcc 의 동작).

  • 상태에서 안 while:위 내용을 참조하십시오.하지만 이상한 일이 일어나는 여기:이 경우에는 gcc 수 있도록 보인 1 가지 원다.

코드를 증명할 수 있습니다 암호:당신이 관심이 있다면 및 설명이 필요하는 것을 망설이지 마십시오 묻는다-나는 그 곳.

@ΤΖΩΤΖΙΟΥ

에 답변을 ΤΖΩΤΖΙΟΥ's 의견에,내가 존재하는 수정된 버전의 위의에 따라 상한 비트의 폭입니다.

#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
    TYPE m=~0;
    switch(bits)
    {
        case 64:
            x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
        case 32:
            x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
        case 16:
            x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
        case 8:
            x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
            x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
            x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
    }
    return x;
}

int main(int argc, char**argv)
{
    TYPE x;
    TYPE b = (TYPE)-1;
    int bits;
    if ( argc != 2 ) 
    {
        printf("Usage: %s hexadecimal\n", argv[0]);
        return 1;
    }
    for(bits=1;b;b<<=1,bits++);
    --bits;
    printf("TYPE has %d bits\n", bits);
    sscanf(argv[1],"%x", &x);

    printf("0x%x\n",reverse(x, bits));
    return 0;
}

Notes:

  • gcc 경고에서 64 비트 상수
  • 이 printfs 생성됩니다 너무 경고
  • 더 필요한 경우에는 64 비트 이상의 코드 간단해야 충분히 확장

I 행에 필요한 코딩 범죄에 내가 위의 자비에 좋은 선생님!

가의 좋은 컬렉션에는"만지작거리 해킹"을 포함하여 다양한 간단한 그리 간단한 비트 반전하는 알고리즘 코드에서는 C http://graphics.stanford.edu/~seander/bithacks.html.

나 개인적으로 다음과 같이"분명한"algorigthm(http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious)기 때문에 글쎄,그것은 분명합니다.일부는 다른 사람의 필요할 수 있는 더 적은 지침을 실행합니다.면 나는 정말 최적화가 필요한 지옥의 무언가를 선택할 수 있습니다 그래서 명백하지만 빠른 버전입니다.그렇지 않으면,가독성을 위해 유지 보수성,이식성이 나를 선택할 것이 명백한 하나입니다.

여기에 더 일반적으로 유용한 변형입니다.그것의 장점은 작업을 수행할 수 있다는 상황에서 비트 길이의 값을 반전--코드 워드-알 수 없지만 이상을 초과하지 않는 값에는 maxLength.의 좋은 예를 들어,이 경우 호프만 코드를 압축 해제합니다.

코드는 아래에서 작동 단어에서 1 24 비트 길이입니다.그것은 최적화를 위한 빨리 실행에 Pentium D참고로 그것은에 액세스 조회 테이블의 많은으로 3 시간 사용이다.나는 실험 많은 변화하는 감소하는 숫자 2 개의 비용으로 더 큰 표(4096 및 65,536 항목).이 버전으로,256 바이트는 테이블,었 취소자 부분적으로 있기 때문에,그것은 너무 유리한 테이블 데이터에 캐시고,아마도 때문에 프로세서는 8 비트 테이블 조회/번역을 명령입니다.

const unsigned char table[] = {  
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,  
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,  
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,  
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,  
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,  
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,  
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,  
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,  
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,  
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,  
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,  
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,  
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,  
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,  
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,  
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF};  


const unsigned short masks[17] =  
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};  


unsigned long codeword;   // value to be reversed, occupying the low 1-24 bits  
unsigned char maxLength;  // bit length of longest possible codeword (<= 24)  
unsigned char sc;         // shift count in bits and index into masks array  


if (maxLength <= 8)  
{  
   codeword = table[codeword << (8 - maxLength)];  
}  
else  
{  
   sc = maxLength - 8;  

   if (maxLength <= 16)  
   {
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc];  
   }  
   else if (maxLength & 1)  // if maxLength is 17, 19, 21, or 23  
   {  
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc] |  
                 (table[(codeword & masks[sc]) >> (sc - 8)] << 8);  
   }  
   else  // if maxlength is 18, 20, 22, or 24  
   {  
      codeword = (table[codeword & 0X00FF] << sc)  
               |  table[codeword >> sc]  
               | (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));  
   }  
}

는 방법에 대해:

long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)

while(value > 0)            // loop until value is empty
{
    temp <<= 1;             // shift whatever was in temp left to create room for the next bit
    temp |= (value & 0x01); // get the lsb from value and set as lsb in temp
    value >>= 1;            // shift value right by one to look at next lsb

    counter++;
}

value = temp;

if (counter < number_of_bits)
{
    value <<= counter-number_of_bits;
}

(나는 가정 하는 방법을 알고 있는 많은 비트 값을 보유하고 그것에 저장되 number_of_bits)

분명히 임시될 필요가 가장 긴 상상할 수 있는 데이터 유형을 복사할 때 임시 직원으로 값은,모든 불필요한 비트에 임시해야 하는 마술로 사라진(나는 생각!).

또,'c'방법이 될 것을 말한다:

while(value)

당신의 선택

우리는 저장할 수 있습의 결과 반전이 가능한 모든 1 바이트 시퀀스에서 array(256 별개의 항목),다음의 조합을 사용하여 검색으로 이 테이블과 일부 oring 논리를 얻을 역방향의 정수입니다.

여기에는 변형하고 수정하 TK 의 솔루션이 될 수 있는 보다 선명한 솔루션으로 sundar.그것은 하나의 비트에서 t 으로 그들을 밀어 return_val:

typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8

TYPE reverser(TYPE t)
{
    unsigned int i;
    TYPE return_val = 0
    for(i = 0; i < TYPE_BITS; i++)
    {/*foreach bit in TYPE*/
        /* shift the value of return_val to the left and add the rightmost bit from t */
        return_val = (return_val << 1) + (t & 1);
        /* shift off the rightmost bit of t */
        t = t >> 1;
    }
    return(return_val);
}

의 일반적인 접근 방식 모 작업에 대한 개체의 모든 유형의 크기는 것을 반대로 바이트의 개체,그 반대의 순서의 비트에서 각각의 바이트입니다.이 경우 조금 수준의 알고리즘은 콘크리트의 수는 비트(바이트),"하면서 변수"로직(관한 크기)들을 수준의 전체 바이트입니다.

여기 나의 일반화의 여유 공간의 솔루션(경우에 우리가 하루를 얻을 128-bit 컴).그 결과 점프 코드를 컴파일할 때는 gcc-O3,와 분명히 구분하의 정의 foo_t 에서 제 기계입니다.불행하게도 그것에 의존하지 않습니다 shift 되는 전원의 2!

#include <limits.h>
#include <stdio.h>

typedef unsigned long foo_t;

foo_t reverse(foo_t x)
{
        int shift = sizeof (x) * CHAR_BIT / 2;
        foo_t mask = (1 << shift) - 1;
        int i;

        for (i = 0; shift; i++) {
                x = ((x & mask) << shift) | ((x & ~mask) >> shift);
                shift >>= 1;
                mask ^= (mask << shift);
        }

        return x;
}       

int main() {
        printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}

에서 케이스트-반전이 시간이 중요한,그리고 주로 함께 FFT,최고의를 저장하는 전체 조금 반전의 배열입니다.어떤 경우에,이 배열 될 것이 더 작은 크기 이상의 뿌리 화합야한다는 것을 미리 계산된 측정,쿨리-Tukey 알고리즘이 있습니다.쉽게 계산하는 방법을 배열입니다:

int BitReverse[Size]; // Size is power of 2
void Init()
{
   BitReverse[0] = 0;
   for(int i = 0; i < Size/2; i++)
   {
      BitReverse[2*i] = BitReverse[i]/2;
      BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
   }
} // end it's all
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top