logi sisse meist KKK
3
1

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 20310 = 110010112 -> 001100002 = 4810

Näide: f(153) = 6 või 96, sest 15310 = 100110012 -> 011000002 = 9610 või 000001102 = 610

Näide: f(85) = 0, sest 8510 = 010101012 -> 0

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

küsitud Mar 06 '10 at 23:58

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711


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's gravatar image

egon ♦♦
771239

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 ♦♦

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.

link

vastatud Mar 21 '10 at 23:27

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

edited Mar 27 '10 at 21:29

väikene parandus, mitte erti vaid egon.

(Mar 23 '10 at 15:27) erti 2

palun vabandust

(Mar 24 '10 at 12:53) Ahto Truu ♦♦

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%20Errapart's gravatar image

Andrei Errapart
462

edited May 06 '11 at 11:51

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's gravatar image

risto
1

2

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

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

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);
    }
link

vastatud Mar 14 '10 at 20:30

blinx's gravatar image

blinx
313

edited Mar 15 '10 at 08:22

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Aga mis saab, kui kirjutan Find2Buffers(17)? Vihjeks: arvu 17 kahendkuju on 10001.

(Mar 15 '10 at 08:28) Ahto Truu ♦♦

Paaritust arvust peaks ntz = 0.

(Mar 18 '10 at 21:43) blinx

Ma pidasin silmas seda, et mis saab, kui järjestikuseid vabu puhvreid pole täpselt 2, vaid rohkem...

(Mar 21 '10 at 22:56) Ahto Truu ♦♦

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%202's gravatar image

erti 2
71347

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 ♦♦
Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×7

küsitud: Mar 06 '10 at 23:58

nähtud: 4,264 korda

viimati uuendatud: May 06 '11 at 11:51

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee