Nuputamiseks: Kaks mälupuhvrit

Question

Mälupuhvrite olekuid hoitakse täisarvus bitivektorina, kus 1 tähistab kasutusel olevat ja 0 vaba puhvrit. Leida võimalikult efektiivselt kaks kõrvutist vaba puhvrit.

Tulemus tagastada täisarvuna, milles on 1 leitud puhvrite kohal ja 0 kõigis muudes positsioonides, või kõik bitid 0, kui kaht kõrvutist vaba puhvrit ei olegi.

Võib eeldada, et bitivektor mahub protsessori registrisse, see tähendab, et võib kasutada kõiki tavalisi aritmeetika- ja loogikatehteid.

Näide: f(203) = 48, sest 203₁₀ = 11001011₂ -> 00110000₂ = 48₁₀

Näide: f(153) = 6 või 96, sest 153₁₀ = 10011001₂ -> 01100000₂ = 96₁₀ või 00000110₂ = 6₁₀

Näide: f(85) = 0, sest 85₁₀ = 01010101₂ -> 0

PS. See on meelelahutus, mitte küsimus, mille vastust mulle millekski tegelikult vaja oleks.

Accepted Answer

3

Heaks juhuks kirjutasin natuke vähem loetavamalt:

function f(x: Cardinal): Cardinal; register;
asm
  not eax
  mov edx,eax
  shr edx, 1
  and eax, edx
  bsf ecx, eax
  jz  @@err
  mov eax, 1
  shl eax, cl
  mov edx, eax
  add edx, edx
  or  eax, edx
  ret
@@err:
  xor eax, eax
end;

link

vastatud Mar 07 '10 at 09:42

egon ♦♦
711●3●8

No mis heaks juhuks :)
Kõrgkeeltes tavaliselt bsf/bst operatsioone otseselt ei ole. Java on siinkohal muidugi natuke üllatav erand.

(Mar 07 '10 at 21:35) Ahto Truu ♦♦

D-s on ka näiteks olemas (http://www.digitalmars.com/d/2.0/phobos/std_intrinsic.html)... :D... Kõrgkeeltes saab kasutada (int) lg2(z)... ja kui floatidega tegeleda ei taha siis (http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/)

(Mar 08 '10 at 08:01) egon ♦♦

Answer 2

Kahendsüsteemil põhinevas arvutis saab egoni omaga sarnase lahenduse kirjutada ka ilma bsf/bsr tüüpi käsuta:

C's:

unsigned f(unsigned x) {
    unsigned a = ~x;
    unsigned b = a & (a >> 1);
    if (b == 0) return 0;
    unsigned c = b & (b - 1);
    unsigned d = b ^ c;
    unsigned e = d | (d << 1);
    return e;
}

Pacalis:

function f(x : cardinal) : cardinal;
var a, b, c, d : cardinal;
begin
   a := not x;
   b := a and (a shr 1);
   if b = 0 then begin
      f := 0;
   end else begin
      c := b and (b - 1);
      d := b xor c;
      f := d or (d shl 1);
   end;
end;

Kuidas see töötab:

arvus a = ~x on 1-bitid parajasti vabade puhvrite kohal;
arvus b = a & (a >> 1) on positsioonis i bitt 1 siis, kui arvus a on bitt 1 nii positsioonis i kui ka sellest ühe võrra vasakul (ehk b näitab vabade puhvripaaride asukohti iga paari parempoolsema puhvri järgi);
kui b pole 0, siis on arvus c = b & (b - 1) arvu b parempoolseim 1-bitt asendatud 0-bitiga (sest kui b kahendkuju on ...10...0, siis b - 1 kahendkuju on ...01...1 ja b & (b - 1) kahendkuju seega ...00...0);
eelnevast tulenevalt on arvus d = b ^ c ainult ühes positsioonis 1-bitt ja see on arvu b parempoolseima 1-biti positsioonis;
eelnevast tulenevalt on arvus e = d | (d << 1) täpselt kahes kõrvutiolevas positsioonis 1-bitid ja need on kõige parempoolsemas kohas, kus arvus x on kaks 0-bitti kõrvuti.

Answer 3

2	Sarnaste ülesannete ja probleemide puhul soovitan lugeda Sean Eron Andersoni Bit Twiddling Hacks, väga hariv ja põhjalik ülevaade bitinikerdamise trikkidest. link vastatud May 06 '11 at 11:50 Andrei Errapart 46●2 edited May 06 '11 at 11:51

Answer 4

0

Proovisin leiutada ka ilma tsükklita varianti, kuid ei saanud hakkama.

BITS = 8 # 16 32 64 jne..
MASK = 0b11

def f(x):
    for i in range(BITS - 1):
        if ~(x >> i) & MASK == MASK:
            return MASK << i
    return 0

link

vastatud Mar 07 '10 at 15:35

risto
1

2

Kas if x & (MASK << i) == 0: poleks natuke selgem?

(Mar 07 '10 at 21:36) Ahto Truu ♦♦

Answer 5

c#

using System.Collections;

    BitArray Find2Buffers(int x) {
        BinaryHelper bin = new BinaryHelper();
        int numbits = 0, totalbits = 0;
        int N = 32;
        BitArray result = new BitArray(32);
        while (x != 0 && numbits != N) {
            numbits = bin.Ntz(x);//number of trailing zeroes
            x = x >> numbits;
            totalbits += numbits;
            if (numbits == 2) {
                result.Set(totalbits - 1, true);
                result.Set(totalbits - 2, true);
            }
            numbits = bin.Ntz(~x);//number of trailing ones
            x = x >> numbits;
            totalbits += numbits;
        }
        return result;
    }

    int Ntz(int x) {
        int n = 1;
        if (x == 0)
            return 32;
        if ((x & 0x0000FFFF) == 0) { n = n + 16; x = x >> 16; }
        if ((x & 0x000000FF) == 0) { n = n + 8; x = x >> 8; }
        if ((x & 0x0000000F) == 0) { n = n + 4; x = x >> 4; }
        if ((x & 0x00000003) == 0) { n = n + 2; x = x >> 2; } 
        return n - (x & 1);
    }

Answer 6

0

muide Ahto, sinu lahendus oli mega :P, kust oled saanud selliseid ülesandeid teada? suhteliselt huvitab.

ning Ahto C lahendus annab f(85) puhul vastuseks 384, peaks tulema 0. If kontroll tuleks lisada funktsiooni lõppu, mida säärast: if(e > x) return 0;

link

vastatud Nov 16 '10 at 19:23

erti 2
71●4●7

edited Nov 16 '10 at 21:18

Ülesannete saamisest üldiselt: ma olen programmeerimisvõistlustega tegelenud juba 1988. aastast (alguses võistlejana, hiljem korraldajana); selle ajaga ikka koguneb materjali :)

(Nov 18 '10 at 01:10) Ahto Truu ♦♦

1

Selle ülesande saamisest: sellest tekkis esimesena lahenduse tuumaks olev tähelepanek, et n & (n - 1) on n miinus parempoolseim 1-bitt; see pole minu enda tähelepanek, leidsin selle juba mõne aasta eest raamatust The C Programming Language, autorid B.W.Kernighan ja D.M.Ritchie; väga hea raamat C programmeerijatele, soovitan soojalt.

(Nov 18 '10 at 01:10) Ahto Truu ♦♦

Valest vastusest: tegelikult on ülesande püstitus natuke puudulik, sest funktsioonile f ei anta ette puhvrite arvu; mul läks näidete juures meelest ära märkida, et need on lühiduse huvides tehtud 8-bitise protsessori eeldusel ja suuremate täisarvutüüpide korral loeme ikka, et kõik bitid on võimalikud puhvrid.

(Nov 18 '10 at 01:11) Ahto Truu ♦♦

Nuputamiseks: Kaks mälupuhvrit

Jälgi seda küsimust

Pinu tööpakkumised

Sarnased küsimused