computed column as foreign key allow null
You cannot create the contraint on A.actual_id because it may contains NULLs and there is no PK or unique index.
I didn't touch B because you said you cannot change it.


  Here is what I did. It may work for you:



Create A_data where &lt;> 0, Create A_null when = 0 and your Table B

Create Table dbo.A_data (
    full_id INTEGER NOT NULL PRIMARY KEY,
    actual_id  AS (CASE WHEN (full_id &amp; 0x0F000000) &lt;&gt; 0 THEN full_id &amp;  0x00FFFFFF ELSE NULL END) PERSISTED 
)
Create Table dbo.A_null (full_id INTEGER NOT NULL PRIMARY KEY)
Create Table dbo.B(actual_id int not null)

I can now create a unique index on A_data and a contraints on B which only contains not null value

Create UNIQUE INDEX idx_A_data On dbo.A_data(actual_id)
Go
ALTER Table B WITH CHECK ADD CONSTRAINT fk_a_actual_id FOREIGN KEY(actual_id) REFERENCES A_data(actual_id)
Go

I then create a view A which look like your table A

Create View A with schemabinding as 
    Select full_id, actual_id From dbo.A_data
    union all
    Select full_id, null From dbo.A_null

I finally create a instead of trigger on the view. It will give you the same insert possibilities than your old table A

Create Trigger triggerA on A Instead Of Insert
As
    Insert Into A_data(full_id) 
    select full_id from inserted where (full_id &amp; 0x0F000000) &lt;&gt; 0

    Insert Into A_null(full_id) 
    select full_id from inserted where (full_id &amp; 0x0F000000) = 0

You may also have to create Instead Of Update and Instead Of Delete triggers if required. It is better to keep them separated (1 trigger for each task: insert, delete, update)



  Test


     insert into A(full_id)values(0),(1),(2),(286331153)


0, 1 and 2 go to A_null because (full_id &amp; 0x0F000000) = 0 and 286331153 goes to A_data

A contains:


286331153 / 1118481
0 / NULL
1 / NULL
2 / NULL