java - बस एक पूर्णांक में सभी बिट्स flipping के लिए Bitwise ऑपरेटर?




binary bit-manipulation (10)

मुझे पूर्णांक के बाइनरी प्रतिनिधित्व में सभी बिट्स को फ्लिप करना होगा। दिया हुआ:

10101

आउटपुट होना चाहिए

01010

पूर्णांक के साथ उपयोग किए जाने पर इसे पूरा करने के लिए बिटवाइज़ ऑपरेटर क्या है? उदाहरण के लिए, अगर मैं int flipBits(int n); जैसी विधि लिख रहा था int flipBits(int n); , शरीर में क्या होगा? मुझे केवल फ्लिप करने की आवश्यकता है जो पहले से ही संख्या में मौजूद है, पूर्णांक में सभी 32 बिट्स नहीं।


OpenJDK, Integer.reverse () से कार्यान्वयन:

public static int More ...reverse(int i) {
    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;
}

मेरे लैपटॉप पर मेरे प्रयोगों के आधार पर, नीचे कार्यान्वयन तेज था:

public static int reverse2(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
    i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;

    return i;
}

निश्चित नहीं है कि इसके पीछे क्या कारण है - क्योंकि यह इस बात पर निर्भर करता है कि जावा कोड को मशीन कोड में कैसे समझा जाता है ...


आप यह कोशिश कर सकते हैं:

/**
 * Flipping bits of a decimal Integer.
 */
public class FlipBits {

    public static final char ONE_CHAR = '1';
    public static final char ZERO_CHAR = '0';

    static int flipBits(int n) {
        String nBinary = Integer.toBinaryString(n);
        System.out.println("Original number is decimal " + n + ", and binary  " + nBinary);
        char[] result = new char[nBinary.length()];
        char[] nBinaryChars = nBinary.toCharArray();
        for (int i = 0; i < nBinaryChars.length; i++) {
            result[i] = nBinaryChars[i] == ONE_CHAR ? ZERO_CHAR : ONE_CHAR;
        }
        int resultDecimal = Integer.parseInt(String.valueOf(result), 2);
        System.out.println("Flipped number in decimal is " + resultDecimal
                + ", and in binary is " + String.valueOf(result));
        return resultDecimal;
    }

    public static void main(String[] args) {
        int input = 21;
        int flippedInteger = flipBits(input);
        System.out.println(input + " becomes " + flippedInteger + " after flipping the bits.");
    }

}

नमूना उत्पादन:

मूल संख्या दशमलव 21 और बाइनरी 10101 है
दशमलव में फ़्लिप संख्या 10 है, और बाइनरी में 01010 है
बिट्स फ़्लिप करने के बाद 21 10 बन जाता है।


खैर अब तक वहाँ केवल एक ही समाधान है जो "सही" परिणाम देता है और वह है .. वास्तव में एक अच्छा समाधान नहीं है (अग्रणी शून्य की गणना करने के लिए एक स्ट्रिंग का उपयोग करना; यह मुझे मेरे सपनों में परेशान करेगा;);

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

private static int invert(int x) {
    if (x == 0) return 0; // edge case; otherwise returns -1 here
    int nlz = nlz(x);
    return ~x & (0xFFFFFFFF >>> nlz);
}

private static int nlz(int x) {
    // Replace with whatever number leading zero algorithm you want - I can think
    // of a whole list and this one here isn't that great (large immediates)
    if (x < 0) return 0;
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000) == 0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        n++;
    }       
    return n;
}

जैसा कि हम केवल पूर्णांक के लिए आवश्यक न्यूनतम बिट्स को फ्लिप करने के लिए आवश्यक हैं (कहते हैं कि 50 110010 है और जब औंधा हो जाता है, तो यह 001101 हो जाता है जो 13 है), हम एलएसबी से एमएसबी तक एक समय में व्यक्तिगत बिट्स को उल्टा कर सकते हैं और शिफ्ट कर सकते हैं दाईं ओर बिट्स और तदनुसार 2 की शक्ति लागू करें। नीचे दिया गया कोड आवश्यक कार्य करता है:

int invertBits (int n) {
        int pow2=1, int bit=0;
            int newnum=0;
            while(n>0) {
              bit = (n & 1);
              if(bit==0)
                  newnum+= pow2;
              n=n>>1;
              pow2*=2;
          }
          return newnum;
        }

बस बिटवाइज़र नहीं ऑपरेटर ~ उपयोग करें।

int flipBits(int n) {
    return ~n;
}

कम से कम महत्वपूर्ण बिट्स का उपयोग करने के लिए, इसे सही मास्क में बदलें।
(मुझे लगता है कि आप कम से कम 1 बिट चाहते हैं, यही कारण है कि मुखौटा 1 पर शुरू होता है)

int flipBits(int n, int k) {
    int mask = 1;
    for (int i = 1; i < k; ++i)
        mask |= mask << 1;

    return ~n & mask;
}

जैसा कि Lưu Vĩnh Phúc द्वारा सुझाया गया है, कोई भी लूप का उपयोग करने के बजाय (1 << k) - 1 रूप में मास्क बना सकता है।

int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return ~n & mask;
}

मुझे कुछ उदाहरण देखने होंगे, लेकिन दो पूरक अंकगणित के कारण आपको अप्रत्याशित मूल्य मिल सकते हैं। यदि संख्या में अग्रणी शून्य है (जैसा कि यह 26 के मामले में होगा), ~ ऑपरेटर उन्हें फ्लिप करने के लिए उन्हें अग्रणी बनाएगा - जिसके परिणामस्वरूप एक नकारात्मक संख्या होगी।

इंटर्गर वर्ग का उपयोग करने के लिए एक संभव समाधान होगा:

int flipBits(int n){
    String bitString = Integer.toBinaryString(n);
    int i = 0;

    while (bitString.charAt(i) != '1'){
        i++;
    }

    bitString = bitString.substring(i, bitString.length());

    for(i = 0; i < bitString.length(); i++){
        if (bitString.charAt(i) == '0')
            bitString.charAt(i) = '1';
        else
            bitString.charAt(i) = '0';
    }

    int result = 0, factor = 1;

    for (int j = bitString.length()-1; j > -1; j--){
        result += factor * bitString.charAt(j);
        factor *= 2;
    }

    return result;
}

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

संपादित करें: इस सवाल का पॉलीजेन लुब्रिकेंट्स का उत्तर भी सहायक हो सकता है


यदि आप पूर्णांक में "बिट्स" का उपयोग करना चाहते हैं, तो यह कोशिश करें:

public int flipBits(int n) {
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}

सरल कोड flipping बिट्स को लागू करने के लिए:

#include<stdio.h>

main() {
    unsigned x = 5;
    printf("%u",~x);
}

import java.math.BigInteger;
import java.util.Scanner;

public class CodeRace1 {

    public static void main(String[] s) {
        long input;
        BigInteger num,bits = new BigInteger("4294967295");
        Scanner sc = new Scanner(System.in);
        input = sc.nextInt();
        sc.nextLine();
        while (input-- > 0) {
            num = new BigInteger(sc.nextLine().trim());
            System.out.println(num.xor(bits));
        }
    }
}

public static int findComplement(int num) {
    return (~num & (Integer.highestOneBit(num) - 1));
}






bitwise-operators