Bạn sẽ làm điều đó như thế nào trong C? (Ví dụ: 10110001 trở thành 10001101 nếu chúng ta phải nhân bản 8 bit). Có bất kỳ hướng dẫn nào về một số bộ vi xử lý đơn giản hóa nhiệm vụ này không?bit gương của từ 32 bit
Đó là:
int mirror(int input) {
int returnval = 0;
for (int i = 0; i < 32; ++i) {
bit = input & 0x01;
returnval |= bit;
input >>= 1;
returnval <<= 1;
}
return returnval;
}
Sẽ không trả về kết quả của bạn? –
whops, sửa chữa :) – Simone
'void' function với' return'? :-) –
Nó thực sự gọi là "chút đảo ngược", và thường được thực hiện trong FFT xáo trộn. O (log N) Cách thứ nhất là (lên đến 32 bit):
int reverse(int x, int bits)
{
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x >> (32 - bits);
}
mỗi Giàu Schroeppel trong MIT memo này (nếu bạn có thể đọc quá khứ lắp ráp), sau đây sẽ đảo ngược các bit trong một byte 8 bit cung cấp rằng bạn có số học 64bit có sẵn:
byte = (byte * 0x0202020202ULL & 0x010884422010ULL) % 1023;
Loại quạt nào ra (nhân), chọn chúng (và) và sau đó thu nhỏ lại (mô đun).
Có thực sự là số lượng 8bit mà bạn có không?
Trong khi rất thông minh, trên nhiều nền tảng phân chia ('/') và modulo ('%') là tốn kém, hoạt động đa chu kỳ, đặc biệt nếu nó không phải là sức mạnh của 2 thì trình biên dịch có thể tối ưu hóa thành hoạt động mặt nạ bit. –
Đây là thông minh nhưng phải chậm hơn ít nhất 20 lần so với phương pháp tìm kiếm bảng hiển thị rõ ràng .. –
@R: phụ thuộc vào CPU của bạn. Tôi sẽ đặt cược ba chu kỳ của nó trên một Intel hiện đại, tất cả đều tuân theo các phần song song của đường ống, trong khi phương pháp tiếp cận dựa trên bảng có nhược điểm lớn nhất là chiếm bộ nhớ đệm có giá trị và tệ nhất. trong khi bộ nhớ được truy cập. – Tommy
Tôi nghĩ tôi sẽ tạo một bảng tra cứu các mẫu bitmap 0-255. Đọc từng byte và với bảng tra cứu đảo ngược byte đó và sau đó sắp xếp các byte kết quả một cách thích hợp.
Điều thực sự thú vị là việc tìm kiếm bảng 8 bit có thể được thực hiện trong một lệnh (XLAT) trong hội đồng Intel x86. Không phải là một trong những hướng dẫn nhanh nhất, nhưng nó thực hiện nó trong một hướng dẫn tương đối đơn giản! :-) –
cách tiếp cận nhanh nhất là gần như chắc chắn sẽ được một bảng tra cứu:
out[0]=lut[in[3]];
out[1]=lut[in[2]];
out[2]=lut[in[1]];
out[3]=lut[in[0]];
Hoặc nếu bạn có thể đủ khả năng 128k của bảng dữ liệu (bằng khả năng, tôi có nghĩa là sử dụng bộ nhớ cache cpu, không nhớ chính hoặc sử dụng bộ nhớ ảo), sử dụng đơn vị 16-bit:
out[0]=lut[in[1]];
out[1]=lut[in[0]];
quint64 mirror(quint64 a,quint8 l=64) {
quint64 b=0;
for(quint8 i=0;i<l;i++) {
b|=(a>>(l-i-1))&((quint64)1<<i);
}
return b;
}
chức năng này phản ánh ít hơn 64 bit. Ví dụ, nó có thể phản chiếu 12 bit.
quint64 và quint8 được xác định bằng Qt. Nhưng nó có thể xác định lại nó trong anyway.
Tôi cũng đã tìm ra một giải pháp tối thiểu để phản chiếu 4 bit (một lỗ hổng) chỉ trong không gian tạm thời 16 bit.
mirr = ((orig * 0x222) & 0x1284) % 63
"gương" là từ OK nhưng hầu hết mọi người có thể gọi đó là "đảo ngược bit". –
@GregS: Cảm ơn, điều đó giải thích tại sao tôi gặp khó khăn trong việc googling nó. – Thomas