معرفة عدد البتات اللازمة لتمثيل عدد صحيح موجب في النظام الثنائي؟

Question

ربما يكون هذا أمرًا أساسيًا جدًا، ولكن لتوفير ساعة أو نحو ذلك من الحزن، هل يمكن لأي شخص أن يخبرني كيف يمكنك حساب عدد البتات المطلوبة لتمثيل عدد صحيح موجب معين في Java؟

على سبيل المثالأحصل على العلامة العشرية 11 (1011).أريد الحصول على الجواب، 4.

لقد فكرت إذا كان بإمكاني معرفة كيفية تعيين جميع البتات بخلاف البت الأكثر أهمية على 0، ثم >>> ذلك، سأحصل على إجابتي.لكن...لا أستطبع.

Answer 1

حسنا، يمكنك الاعتماد فقط عدد المرات التي تحول الحق قبل كنت غادرت مع مجرد صفر:

int value = 11;
int count = 0;
while (value > 0) {
    count++;
    value = value >> 1;
}

Answer 2

حسنا، الجواب بسيط جدا. إذا كان لديك قيمة الباحث:

int log2(int value) {
    return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}

والأمر نفسه موجود لونغ ...

[عدل] إذا حلق ميلي ثانية هو القضية هنا، Integer.numberOfLeadingZeros (الباحث) هو كفاءة معقولة، ولكن لا يزال يفعل 15 عملية ... التوسع في كمية معقولة من الذاكرة (300 بايت، ثابت) هل يمكن أن يحلق الى ما بين 1 و 8 عمليات، اعتمادا على مجموعة من الأعداد الصحيحة الخاصة بك.

Answer 3

وبلدي جافا صدئ قليلا، ولكن الجواب الملحد اللغات (إذا كان هناك وظيفة "log2" وظيفة "الكلمة" المتاحة) ستكون كما يلي:

numberOfBits = floor(log2(decimalNumber))+1

وعلى افتراض أن "decimalNumber" هو أكبر من 0. إذا كان 0، تحتاج فقط 1 قليلا.

Answer 4

وInteger.toBinaryString (عدد) مدة العرض ()؛

والحزن جيدة ... لماذا الأصوات أسفل؟

public class Main
{
    public static void main(final String[] argv)
    {
        System.out.println(Integer.toBinaryString(0).length());
        System.out.println(Integer.toBinaryString(1).length());
        System.out.println(Integer.toBinaryString(2).length());
        System.out.println(Integer.toBinaryString(3).length());
        System.out.println(Integer.toBinaryString(4).length());
        System.out.println(Integer.toBinaryString(5).length());
        System.out.println(Integer.toBinaryString(6).length());
        System.out.println(Integer.toBinaryString(7).length());
        System.out.println(Integer.toBinaryString(8).length());
        System.out.println(Integer.toBinaryString(9).length());
    }
}

وإخراج:

1
1
2
2
3
3
3
3
4
4

وهنا هو اختبار بسيط لسرعة مختلف الحلول:

public class Tester 
{
    public static void main(final String[] argv) 
    {
        final int size;
        final long totalA;
        final long totalB;
        final long totalC;
        final long totalD;

        size = 100000000;

        totalA = test(new A(), size);
        totalB = test(new B(), size);
        totalC = test(new C(), size);
        totalD = test(new D(), size);

        System.out.println();
        System.out.println("Total D = " + totalD + " ms");
        System.out.println("Total B = " + totalB + " ms");
        System.out.println("Total C = " + totalC + " ms");
        System.out.println("Total A = " + totalA + " ms");

        System.out.println();
        System.out.println("Total B = " + (totalB / totalD) + " times slower");
        System.out.println("Total C = " + (totalC / totalD) + " times slower");
        System.out.println("Total A = " + (totalA / totalD) + " times slower");
    }

    private static long test(final Testable tester, 
                             final int      size)
    {
        final long start;
        final long end;
        final long total;

        start = System.nanoTime();
        tester.test(size);
        end   = System.nanoTime();
        total = end - start;

        return (total / 1000000);
    }

    private static interface Testable
    {
        void test(int size);
    }

    private static class A
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int value;

            value = 0;

            for(int i = 1; i < size; i++)
            {
                value += Integer.toBinaryString(i).length();
            }

            System.out.println("value = " + value);
        }    
    }

    private static class B
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;

            total = 0;

            for(int i = 1; i < size; i++)
            {
                int value = i;
                int count = 0;

                while (value > 0) 
                {
                    count++;
                    value >>= 1;
                }

                total += count;
            }

            System.out.println("total = " + total);
        }    
    }

    private static class C
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;
            final double log2;

            total = 0;
            log2  = Math.log(2);

            for(int i = 1; i < size; i++)
            {
                final double logX;
                final double temp;

                logX   = Math.log(i);
                temp   = logX / log2;                
                total += (int)Math.floor(temp) + 1;
            }

            System.out.println("total = " + total);
        }    
    }

    private static class D
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;

            total = 0;

            for(int i = 1; i < size; i++)
            {
                total += 32-Integer.numberOfLeadingZeros(i);
            }

            System.out.println("total = " + total);
        }    
    }
}

والناتج على الجهاز الخاص بي هو:

value = -1729185023
total = -1729185023
total = -1729185023
total = -1729185023

Total D = 118 ms
Total B = 1722 ms
Total C = 4462 ms
Total A = 5704 ms

Total B = 14 times slower
Total C = 37 times slower
Total A = 48 times slower

لأولئك منكم تشكو سرعة ... https://en.wikipedia.org / ويكي / Program_optimization # أسعار .

وكتابة البرنامج لتكون قابلة للقراءة أولا، ثم معرفة أين كان بطيئا، ثم جعلها أسرع. قبل وبعد تحسين اختبار التغيير. إذا كان التغيير ليس كبيرا بما فيه الكفاية لحساب مما يجعل رمز أقل قابلية للقراءة لا تهتم التغيير.

Answer 5

وأخذ السجل استنادا اثنين من عدد سيقدم تقريرا عدد البتات المطلوبة لتخزينه.

Answer 6

إذا كنت تحاول تجنب حلقة ويهمك السرعة، يمكنك استخدام أسلوب مثل هذا:

int value = ...;
int count = 0;
if( value < 0 ) { value = 0; count = 32; }
if( value >= 0x7FFF ) { value >>= 16; count += 16; }
if( value >= 0x7F ) { value >>= 8; count += 8; }
if( value >= 0x7 ) { value >>= 4; count += 4; }
if( value >= 0x3 ) { value >>= 2; count += 2; }
if( value >= 0x1 ) { value >>= 1; count += 1; }

وجافا لا يملك الأعداد الصحيحة غير موقعة، بحيث أولا إذا (القيمة <0) أمر مشكوك فيه قليلا. الأرقام السالبة دوما تعيين بت الأكثر أهمية، لذلك يمكن القول تتطلب كلمة كاملة للتمثيلهم. التكيف مع هذا السلوك إذا كنت تهتم.

وبالمناسبة، لمعالجة عدد صحيح 64-بت، استبدل السطر إذا (القيمة <0) مع هذين:

if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }

Answer 7

لقيم غير سلبية، وربما كان الجواب الأكثر مباشرة هي:

java.math.BigDecimal.valueOf(value).bitLength()

و(للأرقام السالبة أنها ستعطي طول قليلا من واحد أقل من القيمة المطلقة، بدلا من اللانهاية التي تتوقعها من اثنين في تدوين تكملة).

Answer 8

أود أن أضيف بعض البدائل الأخرى، فقط من أجل الاكتمال:

1 BigInteger.valueOf(i).bitLength()

ليس سريعًا جدًا.بالإضافة إلى، BigInteger.bitLength() إنه معطل وغير موثوق به (تم إصلاحه في Java7)، منذ أكثر من Integer.MAX_VALUE هناك حاجة إلى وحدات البت (يلزم وجود رقم إدخال مرتفع بشكل غريب!![مثل 1 تحول إلى اليسار Integer.MAX_VALUE مرات، ويعرف أيضا باسم 2^Integer.MAX_VALUE]) تفيض النتيجة وتظهر الأرقام السالبة للتالي 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE أرقام، وهو رقم مرتفع جدًا لدرجة أن رأسك قد ينفجر.لاحظ أنه من المقدر أن الكون يحتوي على حوالي 10^80 ذرة؛هذا الرقم هو 2^4G (G كما في جيجا 1024*1024*1024).

2

static int neededBits(int i)
{
    assert i > 0;
    int res;
    int sh;
    res = ((i > 0xFFFF) ? 1 : 0) << 4;
    i >>= res;
    sh = ((i > 0xFF) ? 1 : 0) << 3;
    i >>= sh;
    res |= sh;
    sh = ((i > 0xF) ? 1 : 0) << 2;
    i >>= sh;
    res |= sh;
    sh = ((i > 0x3) ? 1 : 0) << 1;
    i >>= sh;
    res |= sh;
    res |= (i >> 1);
    return res + 1;
}

حل سريع جدًا، لكنه لا يزال بنصف سرعة عمرك 32 - Integer.numberOfLeadingZeros(i);.

Answer 9

وبحث ثنائي على الدعاه من 2 أسرع من التحول بت ( صوت أعلى الجواب ) الحل الذي قد تكون ذات قيمة إذا كانت الأرقام الضخمة (الآلاف من الأرقام العشرية)، كما تعلمون أقصى بت المتاحة والتي لا تريد لتوليد الجداول:

    int  minExpVal   = 0;
    int  maxExpVal   = 62;
    int  medExpVal   = maxExpVal >> 1;
    long medianValue = 0l;

    while (maxExpVal - minExpVal > 1) {
        medianValue = 1l << medExpVal;
        if (value > medianValue) {
            minExpVal = medExpVal;
        } else {
            maxExpVal = medExpVal;
        }
        medExpVal = (minExpVal + maxExpVal) >> 1;
    }

    return value == 1l << maxExpVal ?  maxExpVal  + 1 : maxExpVal;

ومع ذلك، فإن الحل باستخدام الأصفار البادئة ستظل من أسرع بكثير:

return Long.SIZE - Long.numberOfLeadingZeros(value);

والمقاييس:

Leading zeros time is: 2 ms
BinarySearch time is: 95 ms
BitShift time is: 135 ms

Answer 10

وهذا هو في C، ولكن أظن أنك يمكن أن تتحول إلى جاوة بسهولة إلى حد ما:

العثور على قاعدة سجل 2 من عدد صحيح N-بت في O ( إل جي (N)) عمليات

Answer 11

وماذا عن شيء مثل هذا:

public static int getNumberOfBits(int N) {
    int bits = 0;
        while(Math.pow(2, bits) <= N){
           bits++;
       }
       return bits;
}

وأنا أعلم أنك تبحث عن وسيلة لعدم استخدام الحلقات، ولكن أشعر بأن هذا هو المضيق جدا إلى الأمام إلا منذ بت ليست سوى اثنين إلى قوة عدد.

Answer 12

وهذا واحد يعمل بالنسبة لي!

int numberOfBitsRequired(int n)
{
    return (int)Math.floor(Math.log(n)/Math.log(2)) + 1;
}

لتشمل الأرقام السالبة كذلك، يمكنك إضافة الجزء الضئيل واستخدامها لتحديد علامة.

public static int numberOfBitsRequiredSigned(int n)
{
    return (int)Math.floor(Math.log(Math.abs(n))/Math.log(2)) + 2;
}

Answer 13

ويمكنك أيضا القيام بذلك مثل هذا، إذا كنت لا تريد تعديل القيمة الأصلية.

unsigned int value = 11;
unsigned int count = 0;
if(value > 0)
{
    for(int i=1;i<value;i*=2) // multiply by two => shift one to left
    {
        ++count;
    }
}

ملحوظة: دع القلق مترجم عن تحويل i*=2 في عملية التحول قليلا لتحسين الأداء

.

لالمفكرين البصرية بيننا:

64 32 16  8  4  2  1
 0  0  0  1  0  1  1  -> binary representation of decimal number 'value' = 11 (=1+2+8)

ونبدأ مع i=1 في الحق. ثم واصلنا ضرب من قبل اثنين، لطالما i < value. في غضون ذلك، ونحافظ على مسار وكم بت ذهبنا إلى اليسار.

وحتى في هذا المثال، في أقرب وقت i تصل إلى 16 قيمة أكبر من 11، وبالتالي فإننا تتوقف. وسوف نقوم بعد ذلك تم احصاء 4 بت: 1 *2 *2 *2 *2 = 16 (=2^4)

على حذرا مع الأرقام الموقعة. عند التعامل مع الأرقام وقعت والتي قد تكون إيجابية أو سلبية، سيكون لديك أولا لمضاعفة الأرقام السالبة التي كتبها -1. بالإضافة إلى ذلك، سيكون لديك للنظر في كيفية كنت تريد أن تأخذ علامة بت في الاعتبار.

Answer 14

(int) Math.ceil((Math.log(n) / Math.log(2))

وبالطبع هذا يعمل فقط من أجل الأعداد الصحيحة الموجبة.