Monday, December 8, 2014

Q. 条件分岐や算術演算を使わずに、max(a,b) を計算するプログラムを書けますか?

if文(条件分岐)を使わず、max(a, b) を計算 別解 | 津田の開発な日記」に関連した話です。リンク先のブログ記事では、条件分岐を使わずにmax(a,b)を実装する方法が議論されています。

では、更に条件を厳しくして、「条件分岐も算術演算も使わずに」max(a,b)を実装することはできるでしょうか?























なぜ、「もちろん」なのか。CPUは、ANDやOR、NOTのようなデジタルな論理回路から構成されています。であれば、当然、ビット演算(ビットシフトと&, |, ^)を使って、max(a, b)を実装することも可能なわけです。こんな感じ。

#include <stdio.h>

#define BIT(n, pos) (((n) >> (pos)) & 1)

static int mymax(int a, int b)
{
  int islt = BIT(a, 31) & (BIT(b, 31) ^ 1);
  int iseq = BIT(a, 31) ^ BIT(b, 31) ^ 1;

#define CHECK_BIT(pos) do { \
  islt |= iseq & (BIT(a, pos) ^ 1) & BIT(b, pos); \
  iseq &= BIT(a, pos) ^ BIT(b, pos) ^ 1; \
} while (0)

  CHECK_BIT(30); CHECK_BIT(29); CHECK_BIT(28);
  CHECK_BIT(27); CHECK_BIT(26); CHECK_BIT(25); CHECK_BIT(24);
  CHECK_BIT(23); CHECK_BIT(22); CHECK_BIT(21); CHECK_BIT(20);
  CHECK_BIT(19); CHECK_BIT(18); CHECK_BIT(17); CHECK_BIT(16);
  CHECK_BIT(15); CHECK_BIT(14); CHECK_BIT(13); CHECK_BIT(12);
  CHECK_BIT(11); CHECK_BIT(10); CHECK_BIT(9); CHECK_BIT(8);
  CHECK_BIT(7); CHECK_BIT(6); CHECK_BIT(5); CHECK_BIT(4);
  CHECK_BIT(3); CHECK_BIT(2); CHECK_BIT(1); CHECK_BIT(0);

#undef CHECK_BIT

  /* extend flag to 32-bit mask */
  islt <<= 31;
  islt >>= 31;

  return (a & (islt ^ 0xffffffff)) | (b & islt);
}

int main(int argc, char **argv)
{
  int a, b;

  if (argc != 3) {
    fprintf(stderr, "Usage: %s a b\n", argv[0]);
    return 1;
  }
  if (sscanf(argv[1], "%d", &a) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[1]);
    return 1;
  }
  if (sscanf(argv[2], "%d", &b) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[2]);
    return 0;
  }

  printf("max(%d,%d) is %d\n", a, b, mymax(a, b));

  return 0;
}


11 comments:

  1. I love how you still write and share about your day and experiences! You feel like such a real, nice, and humble person because of this!
    dark souls iii emoji keyboard diep.io slither.io

    ReplyDelete
  2. Live Boxing Stream 2016

    Watch The Boxing Live

    Watch Boxing Online Tv

    Boxing Live Video Stream

    Watch Over 4500 Plus HD Free Channel on Worldwide 2016 Crystal clear coverage is essential so you don’t miss any part of the action. The High Definition(HD) It’s is worldwide Channel coverage and no TV Streaming Online Boxing Streaming.

    ReplyDelete

  3. شركة نقل عفش بالرياض وجدة والدمام والخبر والجبيل اولقطيف والاحساء والرياض وجدة ومكة المدينة المنورة والخرج والطائف وخميس مشيط وبجدة افضل شركة نقل عفش بجدة نعرضها مجموعة الفا لنقل العفش بمكة والخرج والقصيم والطائف وتبوك وخميس مشيط ونجران وجيزان وبريدة والمدينة المنورة وينبع افضل شركات نقل الاثاث بالجبيل والطائف وخميس مشيط وبريدة وعنيزو وابها ونجران المدينة وينبع تبوك والقصيم الخرج حفر الباطن والظهران
    شركة نقل عفش بجدة
    شركة نقل عفش بالمدينة المنورة
    شركة نقل اثاث بالرياض
    شركة نقل عفش بالدمام
    شركة نقل عفش بالطائف

    ReplyDelete