bit값을 뒤집는 좋은 방법 없나요?

IEEE 에서 bit reverse로 journal 검색해보세요.

선지자들의 알고리즘이 많이 있습니다. pseudo code까지 포함해서 말이지요.

256 크기의 배열을 만드시고 인덱스와 원하는 거꾸로의 값으로 채운 다음 필요할 때 그 배열을 참조하시면 바로 답이 나오지 않을까요?

한번 만들어 보았습니다.

#include <stdio.h>

inline unsigned char left_rotate( unsigned char x, int l )
{
        return ((x<<l) & 0xff) | ((x>>(8-l)) & 0xff);
}

int main()
{
        unsigned char x,y;
        x = 0x54; /* expected: 0x2a */
        printf("%x\n", x );
        y = left_rotate( x,4 );
        x = (x & 0xcc) | (y & 0x33);
        y = left_rotate( x,1 );
        x = left_rotate( y,2 );
        y = (x & 0xaa) | (y & 0x55 );
        printf("%x\n", y );
        return 0;
}

좀 난해하죠?

가상적으로 87654321을 놓고 생각하면 편합니다.
bit도 아니고.. 암튼 자리수 채우는 물건입니다.

        x =  87654321
        y = left_rotate( x,4 );         // y = 43218765
        x = (x & 0xcc) | (y & 0x33);  // x = 87214365
        y = left_rotate( x,1 );        // y = 72143658
        x = left_rotate( y,2 );        // x= 14365872
                                        // 오라 x의 홀수번째는 1,3,5,7 y의 짝수번째는 2,4,6,8
        y = (x & 0xaa) | (y & 0x55 );    // 그것들만 가져와서 or하니 12345678!!

 

typedef bitset<numeric_limits<unsigned char>::digts> bitset_t;

가 더 좋겠습니다.

yui 님께서 잘 설명해주셔서 더 설명할 것이 없군요.
rotate, shift, bit 연산이 어셈블리어일때 적당한 알고리즘입니다만,
sodomau 님이 하신것과 성능상 얼마나 좋은지는 모르겠습니다.

일단 가독성은 너무 떨어지고, 그렇다고 연산이 그렇게 작은 것 같지는 않거든요.

htonl 함수같은 구현을 물어 볼때 알고있는 알고리즘이라서 bit 수준에서도 적용해볼까해서 만들어 본 것입니다.

제가 지금 g++를 테스트할 수가 없습니다. 죄송....
제가 최초로 올린 소스는 Borland C++Builder 6으로 컴파일 했고요,
MS Visual C++.NET 2003(7.1)에서 컴파일할 때는
#include <limits>
를 추가해야만 컴파일됩니다.
코드 수정해 놓았습니다.

헤더파일간의 포함 관계는 표준에 정의되어 있지 않기 때문에, 컴파일러에 따라 이런 차이가 생깁니다.

그리고 #pragma hdrstop은 precompiled header에서 제외하는 헤더 파일을 지정하는 것으로, 주로 윈도용 컴파일러에서 사용합니다.
주로, 사용자 정의 헤더 파일이나, 템플릿 라이브러리 헤더파일 앞에 지정하지요.
대응하는 gcc의 #pragma는 잘 모르겠네요. 위 메시지처럼 잘못 지정해도 warning만 날 뿐, 컴파일은 이상없습니다.

bugiii 님 방법 한표!! 8)

흠 제가 지금 맥을 쓰고 있어서 vc 7.1에서는
테스트 할 수 없군요..

.tempalte 혹은 ->template construct가 고안된 이유가 위의 예제와 같은 문맥에서 컴파일러가 '<' 이 문자가 less then인지 아님 template의 시작을 의미하는 문자인지 알 수 있는 방법이 없기 때문임을 생각한다면 vc7.1이 저 코드를 에러없이 컴파일 했다는게 좀 의심스럽군요.

bc++는 표준에 매우 위배되는게 많고 vc는 7.1이 나오면서 template partial specialization 및 기타 6.0의 많은 문제를 해결했다고는 아직 template쪽의 표준을 완전하게는 구현하지 못한것 같습니다. (C++ Templates의 more CRTP 예제를 컴파일 못하더군요) 뭐 gcc도 마찬가지이긴 하지만...

여하튼 reverse_bits 이 함수 여러모로 공부 많이 되서 좋습니다. ^^;

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
bitset<8> num1 = 10;
bitset<8> num2 = 0xff;
string outPut;

num1 ^= num2;

outPut = num1.to_string();
cout << outPut.c_str() << endl;

return 0;
}

가장 간단한 것이 항상 진리는 아닙니다.
여기서는 단지 8비트만 뒤집는 경우이지만, 16, 32, 64비트라면 어떨까요.
비트가 늘어남에 따라 룩업 테이블의 크기는 기하급수적으로 늘어나 버립니다.
임베디드 시스템에서는 아예 구현이 불가능하죠. i8051이나 AVR 같은 8비트 시스템에서는 256바이트 배열을 여러번 쓰는 것도 꽤 부담스러운 일입니다. 그래서 위와 같은 복잡한 비트 연산이 필요할 경우도 있는 겁니다.

std::bitset은 ANSI C++의 표준 라이브러리에 포함되어 있는 기능입니다.
어떤 언어에서든지 표준 라이브러리는 언어의 일부로서, 그 언어를 사용하는 프로그래머에게는 공통적인 어휘 역할을 하는 것입니다.
콘솔 출력을 하기 위해, C에서는 printf, C++에서는 cout <<, Java에서는 System.out.println을 쓰는 것처럼, C++에서의 비트 조작에 bitset을 쓰는 건 너무나 자연스러운 겁니다.
C++ 언어의 특징 때문에 bitset::to_string() 함수를 쓰는 것이 좀 귀찮아서 어렵게 보였을 뿐, 제가 쓴 코드는 상당히 간단한 겁니다.

1. bitset의 내용을 string으로 옮긴다.
2. reverse 알고리듬을 적용한다.
3. 변환된 string을 다시 bitset으로 변환한다.

CPU 사양이 정 안되면 니블 단위로 끊어서 16 바이트크기의 테이블을 구성해서 몇번 반복하면 됩니다. 8 비트 CPU 아니라, 프로그래머블 시퀀서일지라도 할건 해야죠.

게다가 초소형 임베디드 시스템에서는 설령 C/C++ 을 쓰더라도 C 라이브러리까지 쓸수있는 경우는 드뭅니다.

아웅... 너무 심각하게 받아들이지 않으셨으면 합니다. 그냥 이런 저런 방법으로 구현할 수 있겠구나 하고 넘어가시면 좋겠습니다. 그냥 재미삼아 여러가지 구현이 나올 수도 있구요. 그런 와중에 좋은 방법이 나올 수도 있지 않을까요?

하다못해 CPU 종속적인 비트 역전 어셈블리 명령어도 하나의 답글이 될 수도 있습니다. (아예 비트를 역순으로 바꿔주는 명령어가 존재하는 CPU도 있습니다. 8, 16, 32비트 다 되는 걸로 기억합니다.)

특정 비트 유무의 검사를 마스크 배열을 이용해서 해결하거나 이런식의 비트 변경은 임베디드에서 흔히 쓰이는 기법이라 아무 생각없이 말씀드린거니까요. 그럴 수도 있구나 해주시면 좋겠습니다. 하드웨어에서도 어드레스 디코딩 회로를 논리회로로 하지 않고 일반 롬 테이블을 이용해서 무식하게 하는 방법도 있습니다. (물론 배보다 배꼽이 더 큰 경우가 많지만요)

저도 잘못한 것이 그 배열에 어떻게 정확하게 변환값을 집어 넣는가는 빠트린 것입니다. 그런 것을 다른 분들이 올려주신 알고리즘으로 해결하시면 될 것이구요.

중요한 것은 정확한 변환 값을 얻는 것이 먼저라고 생각합니다. 그 후에 좀 더 빠른 변환 알고리즘이나 테이블에 채워서 사용해야 한다고 생각합니다.

이방법이 가장보편적으로 생각할수 있는방법인것 같은데..

typedif struct
{
	unsigned int b1 : 1;
	unsigned int b2 : 1;
	unsigned int b3 : 1;
	unsigned int b4 : 1;
	unsigned int b5 : 1;
	unsigned int b6 : 1;
	unsigned int b7 : 1;
	unsigned int b8 : 1;
} RBIT;

RBIT bits, rbits;

rbits.b1 = bits.b8;
rbits.b2 = bits.b7;
rbits.b3 = bits.b6;
rbits.b4 = bits.b5;
rbits.b5 = bits.b4;
rbits.b6 = bits.b3;
rbits.b7 = bits.b2;
rbits.b8 = bits.b1;

TI의 240x 시리즈 제품은 어드레스 모드중 비트 반전 어드레스를 지원 합니다.
다른 시리즈는 안 다뤄 봐서 보르겠네요.

ruby 버전입니다.

class Integer
  def bitrev(zfill=8)
    ("%0#{zfill}b" % self).reverse.to_i(2)
  end
end

puts "%064b" % (-2**32)
puts "%064b" % (2**32-1)
puts "%064b" % (-2**32).bitrev(64)
puts "%064b" % (2**32-1).bitrev(64)

이건 메모릴 너무 먹겠군요. 4비트에 대해 16개의 테이블로 바꿔치기 하는걸 두번 반복하는게 낫겠습니다.

비트 반전이면

C나 C++경우 ~ 연산자 하나면 끝나는데.....

제가 문제를 잘 못 파악한건지..
뒤늦은 댓글이지만

이 책에 비트 다루는 신기한 공식이 많이 포함되어 있습니다.
비트와 바이트를 뒤집기라는 장이 따로 있을 정도입니다.

x라는 8비트 정수를 뒤집기 위해서는 (절반을 중심으로 반대 위치로 옮기는것)

s = (x* 0x00020202) & 0x01044010
t = (x* 0x00080808) & 0x02088020
결과 = mod(s+t,4095)

이렇게 하면 된다고 하네요 이해는 안되지만 신기하지 않습니까 ^^;
이책을 사놓고 볼 시간이 없어서 안보고 있었는데 이렇게 쓸모가 있네요

변수 하나의 값을 뒤집는 상황이 아니라, unsigned char *array 형의 배열의 원소 전체의 값을 뒤집는 상황에 대해서 조사해 보았습니다. 일반적으로 reverse 함수를 배열의 원소의 수만큼 반복해서 호출해 주어야겠죠. 32비트 CPU인 경우, 이걸 어떻게 좀 효율적으로 처리할 수 없을까 조사하는 중에 재미있는 사실을 알아냈습니다.

unsigned int reverse_8x4( unsigned int c )
{
    c = ((c & 0x55555555) << 1) | ((c >> 1) & 0x55555555);
    c = ((c & 0x33333333) << 2) | ((c >> 2) & 0x33333333);
    c = ((c & 0x0f0f0f0f) << 4) | ((c >> 4) & 0x0f0f0f0f);
 
    return c;
}

함수를 호출할 때, 캐스팅을 사용해서 배열요소 4개를 함꺼번에 32bit 정수형으로 해서 넘겨주게 되면, 각각 8비트 단위로 비트가 뒤집히게 됩니다. 다른 배열요소들을 건드리지 않습니다. 이 알고리즘이 가지는 또다른 장점이겠군요. :-)

unsigned char reverse( unsigned char c ); 형으로 함수를 설계하고 0x55, 0x33 등을 쓰는 것보다 많이 효율적으로 사용할 수 있을 거라 생각합니다.

16비트 배열의 각각의 요소를 뒤집을 경우에는

unsigned int reverse_16x2( unsigned int c )
{
    c = ((c & 0x55555555) << 1) | ((c >> 1) & 0x55555555);
    c = ((c & 0x33333333) << 2) | ((c >> 2) & 0x33333333);
    c = ((c & 0x0f0f0f0f) << 4) | ((c >> 4) & 0x0f0f0f0f);
    c = ((c & 0x00ff00ff) << 8) | ((c >> 8) & 0x00ff00ff);
 
    return c;
}

이런 저런 방식이 많이 나와 있군요..

제가 선호하는 건 굉장히 성능에 critical 한 경우가 아니라면
초보자도 이해가 쉽도록 하는 게 좋다.... 는 ..

잘 배웠습니다. 아.. 근데 글 저장할 수 있는 다른 방법은 없나요..

__asm__ __volatile__ (
    "movb r0, #0x88"          "\n\t"
    "andb r3, r0, %1, ror#1"  "\n\t"
    "andb r4, r0, %1, ror#2"  "\n\t"
    "orrb r3, r3, r4, ror#1"  "\n\t"
    "andb r4, r0, %1, ror#3"  "\n\t"
    "orrb r3, r3, r4, ror#2"  "\n\t"
    "andb r4, r0, %1, ror#4"  "\n\t"
    "orrb %0, r3, r4, ror#3"  "\n\t"
    :"=r"(result)
    :"r"(src)
    :"r0", "r3", "r4"
);

제대로 돌아가는 지는 모르겠지만 대충 이런 느낌으로 코딩하면 될 거 같습니다.

.

속도가 중요하고 정말 byte 만을 대상으로 한다면
아래처럼... 구현하면 되지 않을까요?
php 라면

$table = array("00000000"=>"00000000","00000001"=>"10000000",블라블라,"11111110"=>"01111111","11111111"=>"11111111");
echo $table["00000001"];

#include <stdio.h>
unsigned char table[256]={0x00,0x80,블라블라,0x7F,0xFF};
 
int main(void){
    char a=0x01;
    printf("%x\n",table[a]);
}

어떻게 지우는지 모르겠네요

ㅋ _ ㅋ, 어느 분이 올렸던 포스트를 제가 올려 봅니다.

그런데 질문자분은 왜 for 문을 쓰면 안되나요? for문을 안 쓰고는 되지 않을 듯 싶은뎅?
안되는건 아니지만 어짜피 수동으로 열거 해야 하지 않나요?

=========== 어느 분의 블로그? 에서 ========================
비트를 뒤집어 반대의 숫자 만들기
Posted 2007/04/01 20:13
동아리 후배들이 시스템 프로그래밍이라는 과목을 듣는데, 그 숙제 중에 어려운 문제가 있었는지 모두 끙끙대고 있었습니다. 지금은 고수 형님의 도움으로 모두들 숙제를 끝낸 상태이지만, 차근차근 생각해 보면 그다지 어려운 문제는 아닌지라, 집에서 심심해하다가 제가 한번 풀어 보았습니다.
음, 어떤 16진수 숫자를 입력받으면 그 숫자의 비트를 뒤집어 다른 숫자로 만드는 것이 숙제입니다. 어떤 숫자 123456AB를 입력받으면, 이 숫자를 BA654321로 만드는 게 아니고, 예를 들어 1011010가 그 숫자의 비트면 이걸 0101101로 바꾸는 것입니다. 그러면 전혀 다른 숫자가 나오겠지요. 예를 들어 123456AB일 경우는, D56A2C48이란 숫자가 나와야 합니다.

void main()
{
        int input, answer, temp;
        int compare = 1;
        int count = 0;
        printf("input your hexadecimal number : ");
        scanf("%x", &input);
        for ( count = 0 ; count < 31 ; count++)
        {
                temp = input & compare;
                answer = answer | temp;
                input = input >> 1;
                answer = answer << 1;
        }
        printf("%X\n", answer);
}

compare라는 변수의 값이 1이므로, 비트로 치면 00000000 00000000 00000000 00000001 이고
이걸 입력받은 숫자와 &연산을 했을때 나올 수 있는 숫자는 끝이 0이거나 끝이 1인 두 가지 경우밖에는 없습니다. 이걸 결과 변수와 |연산을 하면(or) 결과에 값을 채워넣을 수 있습니다. 값을 채우면, 입력받은 숫자는 오른쪽으로 시프트, 답을 저장하는 숫자는 왼쪽으로 시프트를 하고 또 다음 숫자와 비교를 합니다. 비트는 int가 4바이트, 즉 32비트이므로 32번 시프트를 하면 모든 비트의 비교가 끝이 나겠습니다.

화살표는 연산한 후에 시프트를 하라는 의미. in=input, com=compare, tem=temp, ans=answer.

it takes a day to make you yawn, brother

======아래는 위 포스트 보기 전 제가 필요해서 만들었던 것 ================

 for(i=0,j=0,k=0;i<=R_BIT_COUNT;i++)
   {
    k=(0x80>>i);
     // 이부분을 참조를 사용한 goto로 작성하면 더욱 빨라질 듯 (비교 없이 곧바로 점프,비트 연산 한번을 줄일수 있다)
    if( ch_a_state_backup&(1<<i))
    {
     j|=k;
    }
   }
/* j 가 결과물 */

제기억에 goto 문 레이블도 참조 테이블로 만들 수 있었던 것 같던데, 그걸 사용하면 위의 것이 for문을 사용한 것 중 가장 빠른
것이 아닐까 생각합니다. 제가 올린 블로그 쓰신 분도 연산 횟수는 제가 만든거와 같습니다. 그런데 그분께 더 장점이 있는게 비트수가
고정되어 있지 않고 제꺼는 고정(0x80)되어 있죠.
그런데 그분 쓰신거에는 비교없이 전부 비트연산을하므로 제가 한 비교를 goto 레이블 룩업으로 변환하여 합치면
가장 빠를 듯.

it takes a day to make you yawn, brother