عكس البت لعدد صحيح، مع تجاهل حجم العدد الصحيح وendianness
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
بالنظر إلى عدد صحيح 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;
}
يحتاج المرء فقط أولاً إلى تشغيلverse_int_setup()، الذي يخزن عددًا صحيحًا بأعلى بت قيد التشغيل، ثم أي استدعاء إلىverse_int(الارجنتين) عائدات الارجنتين مع عكس البتات (لاستخدامها كمفتاح لشجرة ثنائية، مأخوذة من عداد متزايد، ولكن هذا غير ذي صلة إلى حد ما).
هل هناك طريقة غير معتمدة على النظام الأساسي للحصول على القيمة الصحيحة لـ max_int في وقت الترجمة بعد الاتصال بـverse_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.أصبح الكود أكثر كفاءة الآن (مع إزالة الحلقة الداخلية).آمل أن يكون الرمز أيضًا أقل غموضًا هذه المرة.:)
إن الحاجة إلى استخدام العدد هي أن عدد المواضع التي يتعين علينا من خلالها الإزاحة قليلاً يختلف في كل تكرار - علينا تحريك البت الموجود في أقصى اليمين بمقدار 31 موضعًا (بافتراض رقم 32 بت)، والبت الثاني في أقصى اليمين بمقدار 29 موضعًا وهكذا على.ومن ثم يجب أن ينخفض العدد مع كل تكرار مع زيادة i.
نأمل أن تكون هذه المعلومات مفيدة في فهم الكود ...
نصائح أخرى
يعمل البرنامج التالي على إظهار خوارزمية أصغر حجمًا لعكس البتات، والتي يمكن توسيعها بسهولة للتعامل مع أرقام 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;
}
يعمل هذا بشكل جيد في دول مجلس التعاون الخليجي ضمن نظام التشغيل Windows، لكنني لست متأكدًا مما إذا كان مستقلاً تمامًا عن النظام الأساسي.بعض الأماكن المثيرة للقلق هي:
الشرط في حلقة for - يفترض أنه عندما تترك التحول 1 إلى ما هو أبعد من أقصى اليسار، فإنك تحصل إما على 0 مع "سقوط" 1 (ما أتوقعه وما يعطيه Turbo C القديم الجيد iirc)، أو تدور 1 حولك وتحصل على 1 (ما يبدو أنه سلوك دول مجلس التعاون الخليجي).
الحالة في الحلقة الداخلية أثناء:أنظر فوق.ولكن هناك شيء غريب يحدث هنا:في هذه الحالة، يبدو أن gcc يترك الرقم 1 يسقط ولا يدور حوله!
قد يكون الرمز غامضًا:إذا كنت مهتمًا وتحتاج إلى توضيح، من فضلك لا تتردد في السؤال - سأطرحه في مكان ما.
@ΤΖΩΤΖΙΟΥ
ردًا على تعليقات ΤΖΩΤΖΙΟΥ، أقدم نسخة معدلة مما سبق والتي تعتمد على الحد الأعلى لعرض البت.
#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;
}
ملحوظات:
- سوف يحذر مجلس التعاون الخليجي من ثوابت 64 بت
- ستقوم printfs بإنشاء تحذيرات أيضًا
- إذا كنت بحاجة إلى أكثر من 64 بت، فيجب أن يكون الكود بسيطًا بما يكفي للتوسيع
أعتذر مقدمًا عن جرائم التشفير التي ارتكبتها أعلاه - رحمتك سيدي الكريم!
هناك مجموعة رائعة من "Bit Twiddling Hacks"، بما في ذلك مجموعة متنوعة من خوارزميات عكس البت البسيطة وغير البسيطة المشفرة بلغة C في http://graphics.stanford.edu/~seander/bithacks.html.
أنا شخصياً أحب الخوارزمية "الواضحة" (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)
اختيارك
يمكننا تخزين نتائج عكس جميع تسلسلات البايت الممكنة في مصفوفة (256 إدخالًا مختلفًا)، ثم استخدام مجموعة من عمليات البحث في هذا الجدول وبعض منطق القراءة للحصول على عكس العدد الصحيح.
فيما يلي تغيير وتصحيح لحل 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 بت).وينتج عنه تعليمات برمجية خالية من الانتقال السريع عند تجميعها باستخدام gcc -O3، ومن الواضح أنها غير حساسة لتعريف foo_t على الأجهزة السليمة.لسوء الحظ فإنه يعتمد على التحول كونه قوة 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)، فإن الأفضل هو تخزين مصفوفة البتات المعكوسة بالكامل.على أية حال، سيكون حجم هذه المصفوفة أصغر من جذور الوحدة التي يجب حسابها مسبقًا في خوارزمية FFT Cooley-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
