Fast portable arithmetic shifting with C/C++ (to multiply with power-of-two)

There are certain situations when one wants to shift integers either left or right based on runtime parameters, for example to calculate a×2b.

Simply calculating a << b can result in errors:

  • if a is negative, the operation is undefined behavior.
  • if b is negative, the operation is undefined behavior.
  • if a is signed and a 1-bit get shifted in the sign bit, then until C++14 this is undefined behavior and since C++14 it results in the sign-bit being set, which may or may not be desired.
  • with a >> b, if a is negative and b isn’t then the result is implementation defined in C++, it might not be a×2b.

A solution can be the following:

  • Depending on the sign of b, simply do << b or >> (-b).
  • If a is negative and b is positive:
    •   -a       = [1] (-a is positive)
        -a << b  = [2] (-a 2b in a well-defined way)
      -(-a << b) = [3] (-(-a 2b) = a 2b in a well-defined way)
    • In [1], we negate a. This is only undefined if a is the minimum value, for example -128 and can not be converted to +128 in 8 bits. This is the only case which results in UB, but the result would be unrepresentable anyway.
    • In [2], we get –a×2b in a well-defined way and finally in [3] we get a×2b.
  • If a is negative and b is negative:
    •    a        = 1jk..rs..yz  [1] (j..z are the bits)
        ~a        = 0JK..RS..YZ  [2] (N = ~n)
        ~a >> -b  = 00..0JK..RS  [3]
      ~(~a >> -b) = 11..1jk..rs  [4]
    • In [1], we have the original number, a, which is negative.
    • In [2], we get the ones-complement which is abs(a)-1.
    • In [3], we get (abs(a)-1)×2b = abs(a)×2b-1×2b = abs(a)×2b rounded down
    • In [4], we get a×2b-1 where a×2b is rounded up.
    • As it can be seen, this sequence of operations is equivalent to an arithmetic right shift.

The code can be viewed here.

Most platforms implement arithmetic shifting for signed values anyway, meaning they use the arithmetic shift instructions so the above exercise becomes pointless. Even worse, look at the assembly generated here: https://godbolt.org/g/YN1qr4

All the branches are there in the generic shifting function even though they are optimized away to single instructions (SAL, SAR, SHR on x86 and MOV ASL, MOV ASR, MOV LSR on ARM) when the shift amount is known at compile time.

It is best if we rely on builtin arithmetic shifting when possible. To test for this at compile-time, we can verify that shifting -1 = 0xFFFF right by one results in -1. The results can be seen here: https://godbolt.org/g/puIcAF The generic shift function shift_by_int avoids branching and uses less instructions on all platforms.

The code:

#include <type_traits>

template <typename T>
constexpr auto builtin_shr(T value, int amount) noexcept
    -> decltype(value >> amount)
{
    return value >> amount;
}

template <typename T>
struct uses_arithmetic_shift : std::integral_constant<bool, builtin_shr(T(-1), 1) == -1> {};

template <typename T = int>
constexpr T shift_by_portable(T value, int amount) noexcept
{
    return value < 0 ?
      amount < 0 ? ~(~value >> -amount) : -(-value << amount) :
      amount < 0 ? value >> -amount : value << amount;
}

template <typename T = int>
constexpr T shift_by_arithmetic(T value, int amount) noexcept
{
    // Only use with negative T values when the compiler translates right shift to arithmetic shift instructions.
    return amount < 0 ? value >> -amount : value << amount;
}


template <typename T = int>
constexpr T shift_by(T value, int amount) noexcept
{
    return uses_arithmetic_shift<T>::value ? shift_by_arithmetic(value, amount) : shift_by_portable(value, amount);
}

Recreating this with C macros is left as an exercise to the reader.

Évköny: Havonta bő 18,7 kilométerrel az ismeretlen felé

A következő cikket írtam az idei hermanos évkönyvbe a túrázásról.

A Farkas-túrák sokaknak a kikapcsolódás legvégső, legelemibb formáját nyújtották a hermanos évek alatt. A lélekkel a legjobb, mi történhet, ha felkapjuk a vállainkra és egy napig csak a Bükkben túráztatjuk. Ilyenkor a fejnek gondja nincs, csak töltődik fel energiával. És ha már a lélek rávett, hogy szombat reggel nyolckor ott legyél a 15-ös busz diósgyőri végállomásánál, akkor be kell vallani, hogy a testeddel sem történhet jobb annál, mint hogy a nap folyamán teljesen kifacsarod, és estére már csak egy forró fürdőre vágysz lefekvés előtt.

Ezek a túrák valamilyen formában mindig a korlátainkon való túllépésről szóltak. Legyen volt szó az emberi teljesítőképesség, a civilizáció, a járt utak vagy éppen a szigorúan védett természetvédelmi területek határainak átlépéséről, sosem riadtunk vissza. Sokak azóta se voltak olyan hullák, mint a 48-as teljesítménytúra után, de máskor se értünk haza úgy, hogy ne lettünk volna nagyon sárosak, nagyon izzadtak és ne láttunk volna valami legalább olyan csodálatosat, mint a minden fáradságért kárpótló kilátás az Istállós-kő tetejéről.

Nem csak hogy szép helyeket láttunk és mindig jól szórakoztunk, de úgy sem múlhatott el túra, hogy a biológusok és a földrajzosok ne tanulhattak volna valami újat a természet csodáiról Farkas tanár úr jóvoltából. De még ha mondjuk kockázatitőke-befektetőnek is tervezne menni valaki, akkor is megtanulhatta az Elnök úréktól — talán anélkül, hogy észrevette volna –, hogy túrázni milyen csodálatos; és ez a tudás talán jobban meg is ragad — és tán fontosabb is –, mint a dolgozatok után a feledés homályába veszett tananyagrészletek.

Évkönyv: A Hermannapok, amiket jobban élveztünk, mint ők

A következő cikket írtam az idei hermanos évkönyvbe a Hermannapokról.

Az osztályunk természetszerűen próbált menekülni a lehetőség elől, hogy a Hermannapot szervezhesse (ahogyan azt ma is teszik és mindig is tenni fogják más osztályok), de Kóródi tanár úr állhatatosságának köszönhetően miénk lett az első Hermannap szervezésének dicsősége. Akkorra persze már nagyon is gyakorlottak voltunk szervezésben, hiszen elnyertük a Mazsola- és a Kopaszavató szervezésének jogát is (mindkettőt vérre menő küzdelemben), és egy osztálykirándulásnyi kalandtúrát is szerveztünk már egy hatodikos évfolyamnak.

Az első Hermannapon — mindegy, hogy az általunk szervezett elsőre gondolunk vagy a világtörténelemben a legelsőre, mert a kettő ugyanaz –, szóval az első Hermannapon miután túllendültünk a kérdéskörön, hogy mi a francot csináljunk?, valamilyen meseszerű módon mégiscsak összehoztuk a dolgot. Támogatókat kerestünk fel személyesen és győztünk meg, sporteszközöket szereztünk, zenekarokat és táncosokat kértünk fel, tanárainkat is előadásokkal hadra fogtuk, komolyabb grafikai készségek híján pálcikaemberekkel reklámoztuk a rendezvényt. A programokat mind magunk szerveztük, a felügyeletet mind mi láttuk el, például amikor a sorversenyen egyedül részt vevő osztály ellen álltunk ki, hogy ellenfelük legyen.

Hogy az első Hermannap milyen jól sikerült, az utána bekövetkező lincshangulat hiánya és a második ránk sózott Hermannap is mutatja. A második Hermannap kapcsán az osztályból a szervezők közül sokaknak a szívét még ma is elönti a melegség, ha arra gondolnak, hogy aszervező tanárok milyen kreatív és egyedi módokon tudtak tőlünk homlokegynest ellentétes dolgokat kérni.

Tudósok vitatkoznak rajta azóta is, hogy a maga után a földön mindenfelé kívánni valókat hagyó szervezés, a magyarázat nélkül teleportáló projektorok, az egymásra szervezett programok és az általános káosz hogyan végződhetett sikerrel. Pedig, ha a tudósok belegondolnának egy kicsit, rájönnének, hogy tényleg jó programokat szerveztünk: zenekarok, táncosok jöttek, tanárok sztoriztak, mindenféle érdekes játékok, színdarabok voltak, sakkszimultánban, élőcsocsóban és szumóban lehetett részt venni, és persze verőfényes napsütést rendeltünk.

Zoli bácsi és sokak szemében a Hermannapok szervezése valamilyen formában mindenképp a (sokan mások által a hermanos évek csúcsaként számon tartott) Hermanhét két főpróbájaként jelentek meg. Zoli bácsi és a sokak nem csalódhattak: vitathatatlan tény, hogy a Hermannapokkal szerzett és később kamatoztatott tapasztalatainknak volt köszönhető, hogy a Hermanhéten egy percig sem volt kétséges a dobogós helyezésünk.

Az osztályt ugyanis (a már említett tudósokkal ellentétben) sosem érdekelte igazán a programjainak objektív sikeressége — bármit is jelentsen ez –; helyette csak élveztük az egészet. Mi is kipróbáltuk az élőcsocsót, a szumót, egy igazi igazgatóhelyettessel pogóztunk az Attic band kiváló koncertjén, gulyást ettünk, és úgy általában élveztük a ragyogó napsütést. Kafa programokat is szerveztünk előtte, de az mindegy. A Hermanhéten is ugyanezt a tudást kamatoztatta az osztály azzal a különbséggel, hogy akkor több hó esett.

Ha csak nagyon kevés tudás marad meg az egészből, az egész hermanos témából, akkor ez a dolgokat-élvezni-tudás legyen közte — a többi, ami kell, ha kell, jön magától.

Gördülékeny szervezésről

A nagy sikerű koncepciókritika-sorozatot folytatva, ismét az utolsó utáni pillanatban írom le – amikor már nyilván késő – a tutit azzal kapcsolatban, hogy gördülékenyen szervezni hogyan kell dolgokat. Hermannaptól kezdve szalagavatón és osztálykirándulásokon át Hermanhétig bezárólag gyakorlatilag akármit.

Problémák

Mondjuk kezdjük ott, hogyha mindenkinek csak ötletei vannak, akkor azok nem fognak maguktól megvalósulni. Szerencsére ha egy osztálynyi ember szervez dolgokat, akkor lesznek páran, akik automatikusan magukra vállalják pár ötlet megvalósítását.

Maradnak azonban olyan feladatok, amiket senki nem vállal el, amiket többen többféleképp akarnak megvalósítani, és amikhez a többivel összehangolt munkára van szükség. A legelsőre nyilván nem kell példa, a második esetében például egy forgatókönyvre kell gondolni, a harmadik esetben pedig mondjuk a programok reklámozása juthat eszünkbe. Ezen kívül az elvállalt feladatoknak is lehetnek olyan részei, amiket a végrehajtó nem csinál meg automatikusan, például egy költségvetés elkészítése határidőre.

Itt a megoldás!

Ezekre a problémákra a megoldás, hogy választunk egy koordinátort (főszervezőt), aki összefogja az egész projektet. Az ő feladatai a következők:Continue reading “Gördülékeny szervezésről”

Anonymous gitározik

Az egész a karácsonyi ajándékozással kezdődött. Mátét húztam és nem akartam csak a menzáról megmaradt szaloncukrokkal illetve a mikuláscsomagomból megmaradt véletlenszerű csokikkal kiszúrni a szemét.

Az “ajándék” és a “hasznos” két egymást már elméletben kizáró fogalom, így az egésznek azzal indultam neki, hogy ha már valami haszontalan dolgot kell ajándékoznom, akkor legalább magam csinálom, és sokat vesződök vele, hogy ne csak Máténak legyen rossz. Már majdnem előkerült a pincéből az agyag, amikor…Continue reading “Anonymous gitározik”

Hermenhétkoncepció-kritika

Talán valaki már várta is, hogy írjak valamit ilyen címmel; hogy megmondjam a tutit a szokásos hülyeségeimmel együtt a Hermenhétről.

Nekem egy koncepcióm van a Hermanhétre. Nem jó koncepció.* Vagyis az a koncepció, hogy direkt nem jó: rossz, gyenge minőségű, felületes munkát végzünk mindenhol. Hogy messziről látszódjon egy plakáton vagy egy programon, hogy ratyi, és ha ratyi, akkor tudják, hogy az a mienk (akkor is, ha esetleg másik osztályé és úgy ratyi). * Nem, ez tényleg egy rossz, ötlettelen, buta koncepció, csak valamilyen érthetetlen okból tudok érte lelkesedni.

Már egy csomó más ötletet is hallottam olyanoktól, akik azt hiszik, hogy meg akarják csinálni a hermanheti programunkat. Az ötleteket nem tervezem külön kritizálni, vagy ha mégis – ha valami nagyon durvát akarok mondani -, akkor azt mondom majd, “jó ötlet, az enyémmel összevethető.” De nem, tényleg nem fogok kritizálni. Csak fölényesen mosolyogni fogok, amikor a véletlennek köszönhetően az én koncepcióm részleteit látom majd felvillanni. Esetleg majd írok egy dísztáviratot, amelyben megköszönöm, hogy az én ötleteimet valósítottátok meg.

Komolyra fordítva a szót – nem mintha ez eddigieket nem lehetne komolyan venni -, itt van pár gondolat még:

  • Érezzük jól magunkat, játsszuk végig az egészet az esélytelenek nyugalmával
  • Csináljunk egy-két lazulós termet zenével, kajával, teával; hogy legalább jó helyen tudjunk dögleni egy hétig. (Ez annak az ötletnek az ismételt pofátlan ellopása, amit Máté minden páratlan napon elmond.)
  • Költsünk minél kevesebb pénzt programokra (másokra) és később pl. egy búcsú-osztálykirándulás alkalmával minél többet magunkra.
  • Ha esetleg direkt tré imidzset akarnánk felépíteni, akkor az egy olyan dolog, ami nem igényel hónapnyi előkészületeket, és nekem is van már pár ötletem.

(Tudom, nem sok újat mondtam, csak egybeszedtem a gondolataim mai napon hatályos állapotát.)

A tavalyi télbe az volt jó

Hogy hideg volt, és sokat esett a hó.

És ilyen nagy hókupacba lehetett ugrálni nagymamáék erkélyéről. Utána a hókupacból csináltunk Bencével egy szabályos kis igloot, amibe egy ember rendesen elfért.

Egy kis valószínűségszámítás

Feladat:

Mi a valószínűsége, hogy két véletlenszerű egész számot az [1; 10000] intervallumból összeszorozva a kapott eredmény utolsó számjegye 1?

A megoldást a klasszikus valószínűségi mező felállításával kapjuk meg, vagyis olyan elemi eseményekre bontjuk fel az esetet, ahol minden elemi esemény valószínűsége azonos; a valószínűséget pedig a kedvező és az összes esetek hányadosaként kapjuk meg.

Continue reading “Egy kis valószínűségszámítás”

Megváltozott a telefonszámom

Adjatok hozzá a régi telefonszámomhoz 857 232-t.

(Akivel gyakrabban beszélek, azért külön is meg fogom csörgetni.)