मैं बाइट में ऑन बिट्स को कैसे उलट सकता हूं?

मैं जोएल की किताब पढ़ रहा था जहां वह साक्षात्कार के सवाल के रूप में सुझाव दे रहा था:

किसी दिए गए बाइट में "चालू" बिट्स को उल्टा करने के लिए एक प्रोग्राम लिखें।

मैं केवल सी का उपयोग कर समाधान के बारे में सोच सकता हूं।

यहां पूछना ताकि आप मुझे दिखा सकें कि एक गैर सी तरीके से कैसे करें (यदि संभव हो)

0
ro fr bn
सभी 1 एस के खिलाफ एक्सओआर।
जोड़ा लेखक Brad Wilson, स्रोत

17 उत्तर

और यहां एक संस्करण सीधे OpenJDK से काटा और चिपकाया गया है, जो दिलचस्प है क्योंकि इसमें कोई लूप शामिल नहीं है। दूसरी तरफ, मैंने पोस्ट किए गए स्कीम संस्करण के विपरीत, यह संस्करण केवल 32-बिट और 64-बिट संख्याओं के लिए काम करता है। :-)

32-बिट संस्करण:

public static int reverse(int i) {
   //HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

64-बिट संस्करण:

public static long reverse(long i) {
   //HD, Figure 7-1
    i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
    i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
    i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
    i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
    i = (i << 48) | ((i & 0xffff0000L) << 16) |
        ((i >>> 16) & 0xffff0000L) | (i >>> 48);
    return i;
}
0
जोड़ा

चूंकि प्रश्न गैर-सी तरीके से पूछे जाने के बाद, यहां एक योजना कार्यान्वयन है, जो SLIB </से हर्षित रूप से चोरी की गई है। एक>:

(define (bit-reverse k n)
  (do ((m (if (negative? n) (lognot n) n) (arithmetic-shift m -1))
       (k (+ -1 k) (+ -1 k))
       (rvs 0 (logior (arithmetic-shift rvs 1) (logand 1 m))))
      ((negative? k) (if (negative? n) (lognot rvs) rvs))))

(define (reverse-bit-field n start end)
  (define width (- end start))
  (let ((mask (lognot (ash -1 width))))
    (define zn (logand mask (arithmetic-shift n (- start))))
    (logior (arithmetic-shift (bit-reverse width zn) start)
            (logand (lognot (ash mask start)) n))))

सी के रूप में लिखे गए (लोगों के लिए योजना से अपरिचित लोगों के लिए), यह ऐसा कुछ दिखाई देगा (समझ में कि योजना में, संख्याएं मनमाने ढंग से बड़ी हो सकती हैं):

int
bit_reverse(int k, int n)
{
    int m = n < 0 ? ~n : n;
    int rvs = 0;
    while (--k >= 0) {
        rvs = (rvs << 1) | (m & 1);
        m >>= 1;
    }
    return n < 0 ? ~rvs : rvs;
}

int
reverse_bit_field(int n, int start, int end)
{
    int width = end - start;
    int mask = ~(-1 << width);
    int zn = mask & (n >> start);
    return (bit_reverse(width, zn) << start) | (~(mask << start) & n);
}

0
जोड़ा

मैं शायद गलत समझा रहा हूं, लेकिन मैं   सोचा कि जोएल का सवाल था   बजाय "ऑन" बिट्स की गिनती   उन्हें उलट रहा है।

हेयर यू गो:

#include 

int countBits(unsigned char byte);

int main(){
  FILE* out = fopen( "bitcount.c" ,"w");

  int i;
  fprintf(out, "#include \n#include \n#include \n\n");

  fprintf(out, "int bitcount[256] = {");
  for(i=0;i<256;i++){
    fprintf(out, "%i", countBits((unsigned char)i));
    if( i < 255 ) fprintf(out, ", ");
  }
  fprintf(out, "};\n\n");

  fprintf(out, "int main(){\n");

  fprintf(out, "srand ( time(NULL) );\n");
  fprintf(out, "\tint num = rand() %% 256;\n");
  fprintf(out, "\tprintf(\"The byte %%i has %%i bits set to ON.\\n\", num, bitcount[num]);\n");

  fprintf(out, "\treturn 0;\n");
  fprintf(out, "}\n");
  fclose(out);

  return 0;
}

int countBits(unsigned char byte){
  unsigned char mask = 1;
  int count = 0;
  while(mask){
    if( mask&byte ) count++;
    mask <<= 1;
  }
  return count;
}
0
जोड़ा

सी # में बिट्स के क्रम को उलटाना:

byte ReverseByte(byte b)
{
    byte r = 0;
    for(int i=0; i<8; i++)
    {
        int mask = 1 << i;
        int bit = (b & mask) >> i;
        int reversedMask = bit << (7 - i);
        r |= (byte)reversedMask;
    }
    return r;
}

मुझे यकीन है कि ऐसा करने के अधिक चालाक तरीके हैं लेकिन उस सटीक मामले में, साक्षात्कार प्रश्न यह निर्धारित करने के लिए है कि क्या आप बिटवाई ऑपरेशंस जानते हैं, इसलिए मुझे लगता है कि यह समाधान काम करेगा।

एक साक्षात्कार में, साक्षात्कारकर्ता आम तौर पर जानना चाहता है कि आपको समाधान कैसे मिलता है, आप समस्या निवारण कौशल क्या हैं, अगर यह साफ है या यह हैक है। तो एक चतुर समाधान के साथ बहुत अधिक न आएं क्योंकि यह शायद का अर्थ है कि आपने इसे पहले कहीं इंटरनेट पर पाया है। नकली करने की कोशिश न करें कि आप इसे नहीं जानते हैं और न ही आप जवाब के साथ आते हैं क्योंकि आप एक प्रतिभाशाली हैं, यदि वह मूल रूप से झूठ बोलने के बाद से पता चलता है तो यह भी सबसे खराब होगा।

0
जोड़ा

उस सवाल का क्या अर्थ है?

क्या रिवर्स का मतलब है 1 से 0 के सेटिंग और इसके विपरीत?

Or does it mean 00001100 --> 00110000 where you reverse their order in the byte? Or perhaps just reversing the part that is from the first 1 to the last 1? ie. 00110101 --> 00101011?

मान लीजिए कि पूरे बाइट में बिट ऑर्डर को उलटना है, यहां एक x86 असेंबलर संस्करण है:

; al is input register
; bl is output register

xor bl, bl      ; clear output

; first bit
rcl al, 1       ; rotate al through carry
rcr bl, 1       ; rotate carry into bl

; duplicate above 2-line statements 7 more times for the other bits

सबसे इष्टतम समाधान नहीं, एक टेबल लुकअप तेज है।

0
जोड़ा

उस प्रश्न का विशेष रूप से क्या अर्थ है?

अच्छा प्रश्न। यदि "ऑन" बिट्स को उलट करने का अर्थ केवल "चालू" बिट्स को उलट देता है, तो आप हमेशा 0 प्राप्त करेंगे, इससे कोई फर्क नहीं पड़ता कि इनपुट क्या है। यदि इसका मतलब है कि सभी बिट्स को उलटना, यानी सभी 1s से 0s और सभी 0s से 1s को बदलना, जिस तरह से मैंने इसे प्रारंभ में पढ़ा है, तो यह थोड़ा सा नहीं है, या पूरक है। सी-आधारित भाषाओं में पूरक ऑपरेटर होता है, ~ , जो यह करता है। उदाहरण के लिए:

unsigned char b = 102;      /* 0x66, 01100110 */
unsigned char reverse = ~b; /* 0x99, 10011001 */
0
जोड़ा

क्लासिक बिट हैक्स पृष्ठ में ऐसा करने के लिए कई (वास्तव में बहुत चालाक) तरीके हैं, लेकिन यह सी में है। सी सिंटैक्स (विशेष रूप से जावा) से व्युत्पन्न कोई भी भाषा में समान तरीके होंगे। मुझे यकीन है कि हमें इस धागे में कुछ हास्केल संस्करण मिलेंगे;)

0
जोड़ा

बाइट रिवर्सबाइट (बाइट बी)   {       वापसी बी ^ 0xff;   }

यह काम करता है अगर ^ आपकी भाषा में एक्सओआर है, लेकिन यदि यह और है, जो अक्सर होता है।

0
जोड़ा

यदि आप रूबी का उपयोग करके 1 से 0 के 0 और 0 से 1 तक स्विच करने के बारे में बात कर रहे हैं:

n = 0b11001100
~n

यदि आपका मतलब है कि आदेश को उलट दें:

n = 0b11001100
eval("0b" + n.to_s(2).reverse)

यदि आप किसी अन्य उपयोगकर्ता द्वारा उल्लिखित बिट्स पर गिनती का मतलब है:

n = 123
count = 0
0.upto(8) { |i| count = count + n[i] }

? माणिक

0
जोड़ा

छद्म कोड ..

while (Read())
  Write(0);
0
जोड़ा

बिट्स को उलटाना उदाहरण के लिए हमारे पास 01101011 द्वारा प्रतिनिधित्व किया गया एक नंबर है। अब अगर हम बिट्स को उलट देते हैं तो यह नंबर 11010110 बन जाएगा। अब इसे प्राप्त करने के लिए आपको सबसे पहले पता होना चाहिए कि संख्या में दो बिट्स कैसे स्वैप करें। एक संख्या में दो बिट्स स्वैपिंग: - एक्सओआर दोनों के साथ बिट्स और देखें कि परिणाम अलग हैं या नहीं। यदि वे नहीं हैं तो दोनों बिट्स समान हैं अन्यथा XOR दोनों XOR के साथ बिट्स और इसे मूल संख्या में सहेजते हैं; अब संख्या को उलटाने के लिए मैं संख्याofbits/2 से कम के लिए    स्वैप (संख्या, मैं, NumberOfBits-1-मैं);

0
जोड़ा

मैं चाल सवाल का दावा करता हूं। :) सभी बिट्स को उलटना एक फ्लिप-फ्लॉप का मतलब है, लेकिन केवल बिट्स जो स्पष्ट रूप से हैं:

return 0;
0
जोड़ा

बिट्स के पूरक के लिए अनिवार्य हास्केल सोलन यहां है, यह लाइब्रेरी फ़ंक्शन का उपयोग करता है, पूरक:

import Data.Bits
import Data.Int

i = 123::Int
i32 = 123::Int32
i64 = 123::Int64
var2 = 123::Integer

test1 = sho i
test2 = sho i32
test3 = sho i64
test4 = sho var2 -- Exception

sho i = putStrLn $ showBits i ++ "\n" ++ (showBits $complement i)
showBits  v = concatMap f (showBits2 v) where
   f False = "0"
   f True  = "1"
showBits2 v = map (testBit v) [0..(bitSize v - 1)]
0
जोड़ा

यहां पूछना ताकि आप मुझे दिखा सकें कि गैर-मार्ग (यदि संभव हो) में कैसे करें

मान लें कि आपके पास 10101010 नंबर है। 1 से 0s (और इसके विपरीत) को बदलने के लिए आप बस एक्सओआर का उपयोग करें:

 10101010
^11111111
 --------
 01010101

हाथ से ऐसा करना "गैर सी" जैसा है जैसा आपको मिलेगा।

हालांकि सवाल के शब्द से यह वास्तव में लगता है कि यह केवल बिट्स को बंद कर रहा है ... जिस स्थिति में उत्तर शून्य है (जैसा कि पहले से ही उल्लेख किया गया है) (जब तक कि निश्चित रूप से प्रश्न नहीं है वास्तव में बिट्स के आदेश स्वैप करने के लिए पूछना)।

0
जोड़ा

यदि प्रश्न सभी बिट्स को फ़्लिप करने का मतलब है, और आपको सीओ जैसे ऑपरेटर जैसे एक्सओआर और नोट का उपयोग करने की अनुमति नहीं है, तो यह काम करेगा:

bFlipped = -1 - bInput;
0
जोड़ा

मैं शायद गलत समझा रहा हूं, लेकिन मैंने सोचा कि जोएल का सवाल उन पर वापस आने के बजाए "ऑन" बिट्स पर गिनती के बारे में था।

0
जोड़ा

मैं पाल्मेसी के दूसरे उदाहरण को संशोधित करता हूं, एक बग को हटाता हूं और eval को समाप्त करता हूं:

n = 0b11001100
n.to_s(2).rjust(8, '0').reverse.to_i(2)

rjust महत्वपूर्ण है यदि संख्या bitwise-reversed होने के लिए एक निश्चित-लंबाई बिट फ़ील्ड है - इसके बिना, 0b00101010 के विपरीत 0b10101 </कोड> सही 0b01010100 के बजाय। (जाहिर है, 8 को प्रश्न में लंबाई के साथ प्रतिस्थापित किया जाना चाहिए।) मैं बस इस से टकरा गया।

0
जोड़ा